(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 i. 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 0 \leq j \leq i-1, 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: