Longest Substring Without Repeating Characters – LeetCode Solution [Medium]

Problem

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

LeetCode Problem Link

Input

String s consisting of English letters, digits, symbols and spaces.

Output

Length of the longest substring without repeating characters of string s

Constraints

  • 0 <= Length of s ≤ 5 * 104

Sample Input

s = "pwwkew"

Sample Output

3
The answer is "wke", with the length of 3.

Solution

Approach: Sliding Window Technique and hashing

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int *charMap = new int[300]();
        int n = s.size();
        int maxSoFar = 0;
        int maxSol = 0;
        int prev = 0;
        
        if(s.size() <= 1) {
            return s.size();
        }
        
        for (int i=0; i<300; i++) {
            charMap[i] = -1;
        }
        
        for (int i=0; i<n; i++) {
            if (charMap[s[i]] == -1) {
                maxSoFar++;
                charMap[s[i]] = i;
            } else {
                prev = max(prev, charMap[s[i]]);
                maxSoFar = i-prev;
                charMap[s[i]] = i;
            }
            maxSol = max(maxSol, maxSoFar); 
        }
        return maxSol;
    }
};

Time complexity: O(n), where n is the length of string s

Leave a Reply

Your email address will not be published.