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

If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment