Longest Substring Without Repeating Characters Problem

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.

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;
}