Clash Royale CLAN TAG

Longest unique substring

This question may seem repeated but I am posting it since I was not able to find the solution that I wanted.
If the input string is "abcaadafghae", I want the first longest unique substring (without repeated characters) which should be "dafgh". I got the below program for finding the length of this substring which is 5, but I want the substring itself as the output.

Thanks in advance.

int lengthOfLongestSubstring(string s) {
int n = s.length();
int i = 0, j = 0;
int maxLen = 0;
bool exist[256] = { false };
while (j < n) {
if (exist[s[j]]) {
maxLen = max(maxLen, j-i);
while (s[i] != s[j]) {
exist[s[i]] = false;
i++;
}
i++;
j++;
} else {
exist[s[j]] = true;
j++;
}
}
maxLen = max(maxLen, n-i);
return maxLen;
}


2 Answers
2

Assuming that this is a learning exercise, here is how you can modify your algorithm to find the longest unique substring.

Start by identifying the places in your code where you modify maxLen. There are three of them:

maxLen

max(maxLen, j-i)

max(maxLen, n-i)

Replace maxLen with maxStr, and use it as follows:

maxLen

maxStr

max(maxLen, j-i)

maxStr.length() < (j-i)

maxStr

s

i

j

max(maxLen, n-i)

maxStr.length() < (n-i)

maxStr

s

i

n

Return maxStr, that would be your answer.

maxStr

Demo.

/*C++ program to print the largest substring in a string without repetation of character.
eg. given string :- abcabbabcd
largest substring possible without repetition of character is abcd.*/

#include<bits/stdc++.h>
using namespace std;
int main()
{
string str,str1;
int max =0;
string finalstr;
vector<string> str2;
cin>>str;
int len = str.length();
for(int i=0;i<len;i++)
{
if(str1.find(str[i]) != std::string::npos)
{
str2.push_back(str1);
char p = str[i];
str1 = "";
i--;
while(p!=str[i])
i--;
}
else
str1.append(str,i,1);
}
str2.push_back(str1);

for(int i=0;i<str2.size();i++)
{
if(max<str2[i].length()){
max = str2[i].length();
finalstr = str2[i];
}
}
cout<<finalstr<<endl;
}


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.