Leetcode - Longest Substring Without Repeating Characters

Leetcode : Longest Substring Without Repeating Characters

Description

Given a string s, find the length of the longest substring without repeating characters.

Example 1

Input

s = "abcabcbb"

Output

3
// The answer is "abc", with the length of 3

Example 2

Input

s = "bbbbb"

Output

1
// The answer is "b", with the length of 1

Example 3

Input

s = "pwwkew"

Output

3
// The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring

Approach

Hash table can be used to match the correspoding length of maximum substring. However, for this problem substring method (i.e - s[i:i+1]) to eliminate a duplicate value within the string.

Solutions

Solution I (Python)

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        subStr = ""
        maxLen = 0 

        for i in range(len(s)):
            if s[i] in subStr:
                index = subStr.index(s[i])
                subStr = subStr[index+1:i]
            subStr = subStr + s[i]

            if maxLen < len(subStr):
                maxLen = len(subStr)

        return maxLen

Result

Runtime: 48 ms
Memory Usage: 13.7 MB
Runtime Beats 73.56% of Python Submission

Solution II (JavaScript)

var lengthOfLongestSubstring = function(s) {
    var start = 0,
        temp = '',
        result = ''
    for (let i = 0; i < s.length; i ++) {
        let index = temp.indexOf(s[i])
        if (index !== -1) {
            start = start + index + 1
        }
        temp = s.substring(start, i + 1)
        if (result.length < temp.length) {
            result = temp
        }
    }
    return result.length
};

Result

Runtime: 84 ms
Memory Usage: 37.6 MB
Runtime Beats 99.64% of Python Submission