 # LONGESTNONRE -Editorial

Practice

Author: Kunal Demla
Editorialist: Kunal Demla

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