all articles

leetcode war 3 - Longest Substring Without Repeating Characters

2016-09-17 @sunderls

leetCode

following solutions are all created by myself, if I didn't tackle it and got solution from editorial solution, it will be made clear at the heading.

leetcode war :Longest Substring Without Repeating Characters

https://leetcode.com/problems/longest-substring-without-repeating-characters/

Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

analysis

  1. we have to traverse all the characters, by a range, trying to get the longest range. Firstly we set range's start at index:0, and move the end index.
  2. if we encounter a repeating character, we have found a possible longest non-repeating substring. After that we have to set start index right after first occurrence of the repeating character.
  3. how to judge reoccurrence of a character? if we do it by search, it is slow, we can swap time into space, using a hashmap to quickly determine the first occurrence of a target character.

example "pwwkew"

  1. [0, 0] => "p", max length 1, map { p : 0}
  2. next char: w, not in map, enlarge the range: [0, 1], maxlength 2, map: {p:0, w: 1}
  3. next char: w, in map at 1, set range to [0 + 1 + 1, 2], maxlength 2, map: {w: 2}
  4. next char: k, not in map, enlarge range: [2, 2 + 1], maxlength 2, map: {w:2,k: 3}
  5. next char: e, not in map, enlarge range: [2, 3 + 1], maxlength 3, map: {w:2,k:3,e:4}
  6. next char: w, in map, set range to [2 + 0, 4 + 1], maxlength 3, map: {k:3, e,4, w: 5}
  7. end

pseudo code

start = 0, end = 1, maxlength = 1, map = {}
while end < length:
    if charAt(end)  in map:
        maxlength = max(end - start, maxlength)
        start = firstIndex + 1
        update map
    else 
        end += 1

complexity

every character have to be checked max 2 times (in map or not, update map), O(n) in time & O(n) in space.

code

I've edited 4 times to get the following accepted code. Run at 235ms;


var lengthOfLongestSubstring = function(s) {
    var length = s.length;
    // set end from 0 can avoid empty string check
    var start = 0, end = 0, maxSubStringLength = 0;
    var char, indexMap = {}, indexFound;

    while (end < length){
        char = s[end];
        indexFound = indexMap[char];
        if (indexFound !== undefined){
            maxSubStringLength = Math.max(end - start, maxSubStringLength);
            for(var i = start; i <= indexFound; i++){
                delete indexMap[s[i]];
            }
            start = indexFound + 1;
        }

        indexMap[char] = end;
        end++;
    }

    // have to check the ending case
    maxSubStringLength = Math.max(end - start, maxSubStringLength);

    return maxSubStringLength;
};

Editorial Solution

Editorial Solution firstly introduces brute force solution which is not considerable, and gives us Sliding Window and optimized one. My solution is exactly the optimized one, and I'm corrected for missing space complexity of O(min(n, m)) to O(n).

Plain Sliding Window algorithm use a Set not Map to detect the duplication, if found the slide start index to next one, rather than the reoccurrence index from the map.

And from Editorial Solution, if we suppose that input string are made up fro ASCII code(0~ 255), we can use a less cost int array rather than a hashmap, oh yes, direct access, cool.

Commonly used tables are: int[26] for Letters 'a' - 'z' or 'A' - 'Z' int[128] for ASCII int[256] for Extended ASCII