LONGESTNONRE -Editorial

editorial
1

PROBLEM LINK:

Practice

Author: Kunal Demla
Editorialist: Kunal Demla

DIFFICULTY:

Medium

PREREQUISITES:

Sliding window, two pointer, strings, hashmap

PROBLEM:

Given a string, find the longest substring with non repeating characters

QUICK EXPLANATION:

Parse through, storing the characters being used and the start index, update on every repetition and return max.

EXPLANATION:

We traverse through the string, noting what characters currently make up the chosen substring, if the next element is repetitive, we add that and remove the one we had on earlier.

ALTERNATE EXPLANATION:

Indexes of each can be stored to save time.

SOLUTIONS:

Setter's Solution 
#include<bits/stdc++.h>
using namespace std;
#define ll long long int

void solve()
{
    ll n,m,x,y,i,j,k;
    string s1;
    cin>>s1;
    map<char,int> mp;
    int curr=0,mx=0,start=0,ans1=0,ans2=-1;
    for(int i=0;i<s1.length();i++){
        if(mp[s1[i]]==0){
            curr++;
            mp[s1[i]]++;
        }
        else{
            for(;s1[start]!=s1[i];){
                mp[s1[start]]--;
                start++;
            }
            start++;
            curr=i-start+1;
        }
        if(curr>mx){
            mx=curr;
            ans1=start;
            ans2=i;
        }
    }
    cout<<s1.substr(ans1,ans2-ans1+1);
}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

int t=1;
cin>>t;
int n=t;
while(t--)
{
    solve();
    cout<<"\n";
}

cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" secs"<<endl;
return 0;
}