write java a program that finds the longest substring without repeating characters in a string
bea_1
- 3 Contributors
- forum3 Replies
- 29 Views
- 1 Year Discussion Span
- comment Latest Post by JamesCherrill
JamesCherrill 3,661
OK Bea.
Now go back to the main Programming forum and read the very first post - the one called "Read This Before Posting A Question".
Then come back here and fill in all the missing pieces from your first post.
After that someone will help you.
Badulla
this is a solution which i implemented in an assignment. hope it helps u. also you can use hashsets as well. i have added both code below. the best solution is using hash map.
//first solution to solve
public int lengthOfLongestSubstring(String s) {
if(s==null)
return 0;
boolean[] flag = new boolean[256];
int result = 0;
int start = 0;
char[] arr = s.toCharArray();
for (int i = 0; i < arr.length; i++) {
char current = arr[i];
if (flag[current]) {
result = Math.max(result, i - start);
// the loop update the new start point
// and reset flag array
// for example, abccab, when it comes to 2nd c,
// it update start from 0 to 3, reset flag for a,b
for (int k = start; k < i; k++) {
if (arr[k] == current) {
start = k + 1;
break;
}
flag[arr[k]] = false;
}
} else {
flag[current] = true;
}
}
result = Math.max(arr.length - start, result);
return result;
}
//second but simpler O(n) solution to the problem:
public int lengthOfLongestSubstring(String s) {
HashMap<character, integer=""> map = new HashMap<character, integer="">();
if (s == null || s.length() == 0) return 0;
if (s.length() == 1) return 1;
int rightPointer = 0, leftPointer = rightPointer - 1, answer = 0;
while (rightPointer != s.length()) {
Integer previousOccurrence = map.put(s.charAt(rightPointer), rightPointer);
if (previousOccurrence != null) {
leftPointer = Math.max(leftPointer, previousOccurrence);
}
answer = Math.max(answer, rightPointer - leftPointer);
rightPointer++;
}
return answer;
}
Edited
by Badulla
JamesCherrill 3,661
First version will crash with any Unicode character greater than 256
Second version isn't legal Java. (line 40)
Not sure why the hashmap is a "better" solution. Although O(n) the overheads of the map will swamp a simple nested loop unless the string size is humongously large.