(Longest Substring Without Repeating Characters)

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.

Thoughts:
We want to finish this task in one scan. We can maintain a hashtable to detect if we have seen any character. We start from the beginning and walk through the array until we hit a repetition, let’s say, at position . We then have two piece of valuable information right now:

1. s[0..i-1] is a candidate of the longest substring without repetition. Therefore we can update the max length.
2. There exists a position , such that s[j] == s[i]. Substring starting from j is not a candidate because it has at least one repetition: s[j] and s[i]. Any substring ended at j will be shorter than the substring s[0..i-1] so we don’t need to look at them.

Then we can remove every elements in the hashtable from 0 to j, and make the start position of next candidate to j + 1. We keep walking and repeating this process until we hit the last element.

Code (Java):

import java.util.HashSet;
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int max = 0;
        HashSet<Character> set = new HashSet<Character>();
        int candidateStartIndex = 0;
        for(int iter = 0; iter < s.length(); ++iter) {
            char c = s.charAt(iter);
            if(set.contains(c)) {
                max = Math.max(max, iter - candidateStartIndex);
                while(s.charAt(candidateStartIndex) 
                        != s.charAt(iter)) {
                    set.remove(s.charAt(candidateStartIndex));
                    candidateStartIndex++;
                }
                candidateStartIndex++;
            } else {
                set.add(c);
            }
        }
        max = Math.max(max, s.length() - candidateStartIndex);
        return max;
    }
}

Code (C++):
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unsigned int maxLen = 0;
        set<char> hashtable;
        int candidateStartIndex = 0;
        for(unsigned int iter = 0; iter < s.size(); ++iter) {
            char c = s[iter];
            if(hashtable.find(c) != hashtable.end()) {
                maxLen = max(maxLen, iter - candidateStartIndex);
                while(s[candidateStartIndex] != s[iter]) {
                    hashtable.erase(s[candidateStartIndex]);
                    candidateStartIndex++;
                }
                candidateStartIndex++;
            } else {
                hashtable.insert(c);
            }
        }
        maxLen = max(maxLen, s.size() - candidateStartIndex);
        return maxLen;
    }
};

					

			

				Advertisements