Longest Substring Without Repeating Characters: Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: s = “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.
Example 2:
Input: s = “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.
Example 3:
Input: s = “pwwkew”
Output: 3
Explanation: 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.
Table of Contents
Longest Substring Without Repeating Characters Solution
Problem Solution In Python
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
count = 0
new_str = ""
for i in range(len(s)):
if s[i] not in new_str:
new_str += s[i]
# update the count
count = max(count, len(new_str))
else:
# get the index where the character appears first time in the new string
new_str_index = new_str.index(s[i])
# append this character from original string
new_str += s[i]
#skip first identical character in the new string
new_str = new_str[new_str_index+1:]
return count
Problem Solution In Java
public class Solution {
public int lengthOfLongestSubstring(String s) {
if (s.length() <= 1) return s.length();
int max = 1;
int ptr = 0;
for (int i = 1; i< s.length(); i++) {
// find the first occurence of the char after index ptr
int index = s.indexOf(s.charAt(i), ptr);
if (index < i) { // it means that it is contained in s.substring(ptr, i)
ptr = index + 1;
}
max = Math.max(max, i - ptr + 1);
}
return max;
}
}
Problem Solution In C++
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> umap;
int len =0, j=-1, n = s.length();
for(int i=0;i<n;i++){
if(umap.find(s[i]) != umap.end()){
j = max(umap[s[i]], j);
}
len = max(i-j, len);
umap[s[i]]=i;
}
return len;
}
};
Problem Solution In C
char counts[256];
int lengthOfLongestSubstring(char* s) {
unsigned char *f = (unsigned char *)s;
unsigned char *p = (unsigned char *)s;
unsigned char *next = f;
int longest = 0;
while (*f) {
while ( ! counts [*p] ){
counts[*p]++;
p++;
}
if ( (p-f) > longest )
longest = (p-f);
counts[*f]--;
f++;
}
return longest;
}