Longest Substring Without Repeating Characters

Problem Link:

https://www.geeksforgeeks.org/problems/longest-distinct-characters-in-string5848/1?itm_source=geeksforgeeks&itm_medium=article&itm_campaign=bottom_sticky_on_article

Hint:

• Use an array of size 26 to hash characters with the indexes.

• Initially every alphabet will be 0.

• Iterate through array and if the alphabet is new increase the count of that alphabet.

• If at any point count of an alphabet is more that 0 then it is repeated.

Code:

int longestSubstrDistinctChars (string input)
{
    // your code here
    int n = input.size();
    int maxLen = 1;
    int ind = 0;

    vector<int> hash(26,0);
    // hash[input[0]-'a']++;
    int i = 0;

    while(i<n){
        int p = input[i]-'a';

        if(i==n-1 && hash[p]==0){
            maxLen = max(maxLen, i-ind+1);
        }
        if(hash[p]>0){
            maxLen = max(maxLen, i-ind);

            for(int j=ind;j<i;j++){
                if(input[j]==input[i]){
                    ind = j+1;
                    break;
                }
                hash[input[j]-'a'] = 0;
            }
            i++;
        }
        else{
            hash[p]++;
            i++;
        }
    }
    return maxLen;
}