Back-To-CP: day 10

21-10-2022

Longest Substring Without Repeating Characters

The problem is quite simple if applied brute force, but the time complexity will be O(n^3). So, the good approach is sliding window. Where we keep two pointers at the beginning and a map to store the frequency of the characters in the array. Right pointer keeps moving forward if doesn't encounter the same character twice. If encountered, left pointer will start from the Right pointer position now. This is achieved by in the frequency map, instead of the actual frequency, the position of right pointer is stored. This allows left to jump directly to right + 1.

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.length();
        int ans = 0;
        map<char, int> hmap;
        int left = 0, right = 0;
        while(right<n){
            if(hmap[s[right]] > 0){
                left = max(hmap[s[right]], left);
            }
            ans = max(ans, right-left + 1);
            hmap[s[right]] = right + 1;
            right++;
        }
        return ans;
    }
};