Longest Distinct Substring
Autumn Tournament (2020)
Submission name: strange.cpp
Problem summary
Find the longest contiguous substring whose characters are all different. If several have maximum length, choose the rightmost one. Characters are ASCII codes 33 through 126.
Input
A string s with no spaces.
Output
The maximum length and its zero-based starting position; then the chosen substring.
Constraints
1 ≤ |s| ≤ 20000000.
Worked example
Original statement sample.
Input
abcaacxaa
Output
3 5 cxa
Solution analysis
- Maintain a sliding window [left,right] with no repeated character. last[c] stores the most recent index of character c, initially −1. When reading c at right, move left to max(left,last[c]+1), then update last[c].
- The maximum is essential: an old occurrence before the current window must not move left backwards. After this update, the window is the longest duplicate-free substring ending at right. Record it when its length is greater than or equal to the best length; equality deliberately replaces the earlier answer with the rightmost one.
- For abcaacxaa, the first length-three window is abc at index 0. Later acx starts at 4 and cxa at 5. The last a forces a shorter window. Keeping the latest equal-length candidate yields 3 5 and cxa.
Why it works
When a duplicate occurs inside the window, any distinct substring ending at right must begin after its previous occurrence. Moving left to precisely that boundary preserves all other distinct characters and maximizes the current window. Taking the longest current window over all endpoints finds the global maximum, with the requested rightmost tie-break.
Watch out. Use >= when updating the best window to choose the rightmost tie. Cast a char to unsigned char when indexing. Do not repeatedly scan or erase the window: the input may contain twenty million characters.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<array>
#include<iostream>
#include<string>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
string text;
cin>>text;
array<int,128>last;
last.fill(-1);
int left=0,bestStart=0,bestLength=0;
for(int right=0;right<static_cast<int>(text.size());right++){
unsigned char character=static_cast<unsigned char>(text[right]);
left=max(left,last[character]+1);
last[character]=right;
int length=right-left+1;
// Equality chooses the rightmost longest substring.
if(length>=bestLength){
bestLength=length;
bestStart=left;
}
}
cout<<bestLength<<' '<<bestStart<<'\n';
cout<<text.substr(bestStart,bestLength)<<'\n';
}