0

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

3
Contributors
3
Replies
29
Views
5 Months
Discussion Span
Last Post by JamesCherrill
0

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

0

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.

Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.