Software developers at Amazon are developing a new library for Natural Language Processing. In one of its modules, every string needs to be preprocessed in a particular manner to find the length of its longest self-sufficient proper substring.
A self-sufficient proper substring is one where
-
the substring is not the entire string s
-
no letter that occurs inside the substring also occurs outside the substring
Given the string fullString of length n, find the length of its longest self-sufficient proper substring. If none exists, return 0.
Below is the my solution.
// Online C++ compiler to run C++ program online
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int findLen(vector<int> vis, string &s, int l, int r){
unordered_map<int,int> mp;
for(int i=l; i<=r; i++){
int ind = s[i]-'a';
vis[ind] -= 1;
mp[ind] = 1;
}
for(auto it : mp){
int ind = it.first;
if(vis[ind] != 0) return 0;
}
return r-l+1;
}
int findMax(int st1, int end1, int st2, int end2, vector<int> &vis, string &s){
if(st1 == INT_MAX || st2 == INT_MAX) return 0;
if(st1 > st2) return 0;
// cout<<st1<<" "<<end1<<endl;
// cout<<st2<<" "<<end2<<endl;
// cout<<"---------"<<endl;
int start = 0, end = 0;
if(end2 < end1){
end = end1;
}
else{
end = end2;
}
start = st1;
// if(end == s.size()-1) return 0;
if(start == 0 && end == s.size() - 1) return 0;
int len = findLen(vis, s, start, end);
return len;
}
int solve(string &s){
int n = s.size();
vector<int> vis(26, 0);
vector<int> st(26, INT_MAX);
vector<int> end(26, -1);
for(int i=0; i<n; i++){
int ind = s[i]-'a';
vis[ind] += 1;
st[ind] = min(st[ind], i);
end[ind] = max(end[ind], i);}
int ans = 0;
// cout<<st[25]<<" "<<end[25]<<endl;
// cout<<'s'-'a'<<endl;
// cout<<'z'-'a'<<endl;
for(int i=0; i<26; i++){
for(int j=0; j<26; j++){
// if(i == 25 && j == 18){
int res = findMax(st[i], end[i], st[j], end[j], vis, s);
ans = max(ans, res);
// }
}
}
return ans;
}
int main() {
// Write C++ code here
string s; cin>>s;
int ans = solve(s);
cout<<ans<<endl;
return 0;
}Comments (2)