Problem

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

Example 1:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"
Output: 3
Explanation: 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.

Solution: HashTable + Sliding Window

Using a hashtable to remember the last index of every char. And keep tracking the starting point of a valid substring.

start = max(start, last[s[i]] + 1)

ans = max(ans, i – start + 1)

Time complexity: O(n)

Space complexity: O(128)

C++

// Author: Huahua

class Solution {

public:

int lengthOfLongestSubstring(string s) {

const int n = s.length();

int ans = 0;

vector<int> idx(128, -1);

for (int i = 0, j = 0; j < n; ++j) {

i = max(i,idx[s[j]] + 1);

ans = max(ans, j - i + 1);

idx[s[j]] = j;

}

return ans;

}

};

Java

// Author: Huahua

class Solution {

public int lengthOfLongestSubstring(String s) {

int[] last = new int[128];

Arrays.fill(last, -1);

int start = 0;

int ans = 0;

for (int i = 0; i < s.length(); ++i) {

if (last[s.charAt(i)] != -1)

start = Math.max(start, last[s.charAt(i)] + 1);

last[s.charAt(i)] = i;

ans = Math.max(ans, i - start + 1);

}

return ans;

}

Python3

# Author: Huahua

class Solution:

def lengthOfLongestSubstring(self, s):

last = [-1] * 128

ans = 0

start = 0

for i, ch in enumerate(s):

if last[ord(ch)] != -1:

start = max(start, last[ord(ch)] + 1)

ans = max(ans, i - start + 1)

last[ord(ch)] = i

return ans

Posts tagged as “slding window”

花花酱 LeetCode 3. Longest Substring Without Repeating Characters

Problem

Solution: HashTable + Sliding Window

C++

Java

Python3