strings

[bea_1]

write java a program that finds the longest substring without repeating characters in a string

[JamesCherrill]

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;
}

[JamesCherrill]

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.