fork(4) download
copy 
  1. import java.io.*;
  2.  
  3. // Problem Description: 
  4. // Get the length of longest substring without duplicated characters.
  5. // Supposing all characters in the input are in the range of a to z.
  6.  
  7. class Ideone
  8. {
  9. 	// Solution 1: O(n^3). It gets all (O(n^2)) substrings, and check each
  10. 	// of them whether it contains duplication costing O(n) time
  11. 	public static int longestSubstringWithoutDuplication_1(String str) {
  12. 		int longest = 0;
  13. 		for(int start = 0; start < str.length(); ++start) {
  14. 			for(int end = start + 1; end <= str.length(); ++end) {
  15. 				String substring = str.substring(start, end);
  16. 				if(!hasDuplication(substring) && (end - start > longest)) {
  17. 					longest = end - start;
  18. 				}
  19. 			}
  20. 		}
  21.  
  22. 		return longest;
  23. 	}
  24.  
  25. 	private static Boolean hasDuplication(String str) {
  26. 		int position[] = new int[26];
  27. 		for(int i = 0; i < 26; ++i) {
  28. 			position[i] = -1;
  29. 		}
  30.  
  31. 		for(int i = 0; i < str.length(); ++i) {
  32. 			int indexInPosition = str.charAt(i) - 'a';
  33. 			if(position[indexInPosition] >= 0) {
  34. 				return true;
  35. 			}
  36.  
  37. 			position[indexInPosition] = indexInPosition;
  38. 		}
  39.  
  40. 		return false;
  41. 	}
  42.  
  43. 	// Solution 2: O(n). Dynamic programming. 
  44. 	// When it scans the i^th character in the input,
  45. 	// it checks whether the i^th character has appeared in the 
  46. 	// current longest non-duplication substring, whose length is
  47. 	// curLength in the code. If the character didn't appear before,
  48. 	// the length of the current longest non-duplication substring increases.
  49. 	// Otherwise, the current longest non-duplication substring is updated,
  50. 	// by dropping the characters inclusively before the previous occurance 
  51. 	// of the i^th character, which is the character locating at the index
  52. 	// prevIndex in the code.
  53. 	public static int longestSubstringWithoutDuplication_2(String str) {
  54. 		int curLength = 0;
  55. 		int maxLength = 0;
  56.  
  57. 		int position[] = new int[26];
  58. 		for(int i = 0; i < 26; ++i) {
  59. 			position[i] = -1;
  60. 		}
  61.  
  62. 		for(int i = 0; i < str.length(); ++i) {
  63. 			int prevIndex = position[str.charAt(i) - 'a'];
  64. 			if(prevIndex < 0 || i - prevIndex > curLength) {
  65. 				++curLength;
  66. 			}
  67. 			else {
  68. 				if(curLength > maxLength) {
  69. 					maxLength = curLength;
  70. 				}
  71.  
  72. 				curLength = i - prevIndex;
  73. 			}
  74. 			position[str.charAt(i) - 'a'] = i;
  75. 		}
  76.  
  77. 		if(curLength > maxLength) {
  78. 			maxLength = curLength;
  79. 		}
  80.  
  81. 		return maxLength;
  82. 	}
  83.  
  84. 	//////////////////////////////////////////////////////////////
  85. 	// Test Code Begins
  86. 	//////////////////////////////////////////////////////////////
  87. 	private static void testSolution1(String input, int expected) {
  88. 		int output = longestSubstringWithoutDuplication_1(input);
  89. 		if(output == expected) {
  90. 			System.out.println("Solution 1 passed, with input: " + input);
  91. 		}
  92. 		else {
  93. 			System.out.println("Solution 1 FAILED, with input: " + input);
  94. 		}
  95. 	}
  96.  
  97. 	private static void testSolution2(String input, int expected) {
  98. 		int output = longestSubstringWithoutDuplication_2(input);
  99. 		if(output == expected) {
  100. 			System.out.println("Solution 2 passed, with input: " + input);
  101. 		}
  102. 		else {
  103. 			System.out.println("Solution 2 FAILED, with input: " + input);
  104. 		}
  105. 	}
  106.  
  107. 	private static void test(String input, int expected) {
  108. 		testSolution1(input, expected);
  109. 		testSolution2(input, expected);
  110. 	}
  111.  
  112. 	private static void test1() {
  113. 		String input = "abcacfrar";
  114. 		int expected = 4;
  115. 		test(input, expected);
  116. 	}
  117.  
  118. 	private static void test2() {
  119. 		String input = "acfrarabc";
  120. 		int expected = 4;
  121. 		test(input, expected);
  122. 	}
  123.  
  124. 	private static void test3() {
  125. 		String input = "arabcacfr";
  126. 		int expected = 4;
  127. 		test(input, expected);
  128. 	}
  129.  
  130. 	private static void test4() {
  131. 		String input = "aaaa";
  132. 		int expected = 1;
  133. 		test(input, expected);
  134. 	}
  135.  
  136. 	private static void test5() {
  137. 		String input = "abcdefg";
  138. 		int expected = 7;
  139. 		test(input, expected);
  140. 	}
  141.  
  142. 	private static void test6() {
  143. 		String input = "aaabbbccc";
  144. 		int expected = 2;
  145. 		test(input, expected);
  146. 	}
  147.  
  148. 	private static void test7() {
  149. 		String input = "abcdcba";
  150. 		int expected = 4;
  151. 		test(input, expected);
  152. 	}
  153.  
  154. 	private static void test8() {
  155. 		String input = "abcdaef";
  156. 		int expected = 6;
  157. 		test(input, expected);
  158. 	}
  159.  
  160. 	private static void test9() {
  161. 		String input = "a";
  162. 		int expected = 1;
  163. 		test(input, expected);
  164. 	}
  165.  
  166. 	private static void test10() {
  167. 		String input = "";
  168. 		int expected = 0;
  169. 		test(input, expected);
  170. 	}
  171.  
  172. 	public static void main (String[] args) {
  173. 		test1();
  174. 		test2();
  175. 		test3();
  176. 		test4();
  177. 		test5();
  178. 		test6();
  179. 		test7();
  180. 		test8();
  181. 		test9();
  182. 		test10();
  183. 	}
  184. }
Success #stdin #stdout 0.07s 380160KB
comments (?)
stdin
copy 


			

					
			
			

				
	
		
		
	
		
		 stdout
					

				
				 copy
			

			
	

		
Solution 1 passed, with input: abcacfrar
Solution 2 passed, with input: abcacfrar
Solution 1 passed, with input: acfrarabc
Solution 2 passed, with input: acfrarabc
Solution 1 passed, with input: arabcacfr
Solution 2 passed, with input: arabcacfr
Solution 1 passed, with input: aaaa
Solution 2 passed, with input: aaaa
Solution 1 passed, with input: abcdefg
Solution 2 passed, with input: abcdefg
Solution 1 passed, with input: aaabbbccc
Solution 2 passed, with input: aaabbbccc
Solution 1 passed, with input: abcdcba
Solution 2 passed, with input: abcdcba
Solution 1 passed, with input: abcdaef
Solution 2 passed, with input: abcdaef
Solution 1 passed, with input: a
Solution 2 passed, with input: a
Solution 1 passed, with input: 
Solution 2 passed, with input: 


	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/CmY3xN
					
					
					
					
					

												
Longest substring without duplication

												
						
						

					

					
					
					

						
language:

						
Java (HotSpot 12)

					

					

						
created:
								
						
10 years ago

					

					

						
visibility:

						

							 public																												
							
							

								
							

						

					

										
										

					
					 Share or Embed source code
					
					
					
					

						
						
						
						
						
						
						
					

					
						
	
	
	
	
					
					
					
					
					 
					
					
					
					 
					
					
					
					
					
					

					

					

					
						
					

					


	
Discover > Sphere Engine API

	
The brand new service which powers Ideone!

	
	
Discover > IDE Widget

    
Widget for compiling and running the source code in a web browser!