CODEWITHSUNDEEP
c++string
Tcl_newbie
Tcl_newbie

Reputation: 135

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

Upvotes: 1

Views: 1138

Answers (2)

Vivek Mutha
Vivek Mutha

Reputation: 29

/*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;
}

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726479

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:

  • The place where you set it to zero,
  • The place where you set it to max(maxLen, j-i), and
  • The place where you set it to max(maxLen, n-i)

Replace maxLen with maxStr, and use it as follows:

  • Replace assignment of zero with an assignment to an empty string,
  • Replace assignment to max(maxLen, j-i) with a check maxStr.length() < (j-i), and setting maxStr to substring of s from i, inclusive, to j, exclusive
  • Replace assignment to max(maxLen, n-i) with a check maxStr.length() < (n-i), and setting maxStr to substring of s from i, inclusive, to n, exclusive

Return maxStr, that would be your answer.

Demo.

Upvotes: 3

Related Questions