C++ program to find if a given string has a repeating subsequence of length 2 or more

Given a string, find a subsequence of length at least two that is repeated in the string. The indices of the subsequence element numbers cannot be in the same order.

string s = "PNDPNSP";
print("Repeated subsequence of length 2 or more: ", (check(s) ? "Yes" : "No"));

Let’s look at a few examples below to understand how this approach works in different situations -

Example 1 - str = "PNDPNSP"

Explanation − Here, the answer is true because there is a recurring subsequence "PN" in the string.

Example 2 - str = "PPND"

Explanation - Here, the answer is wrong because there is no repeated subsequence of length at least two in the string.

Example 3 − str = "PPNP"

Explanation - Here, the answer is correct because "PP" indexes 0 and 1 and "PP" indexes 1 and 3 exist, and the "PP" used have different orderings in the subsequence index of. (0-based index)

Brute force Approach

Brute force approach

This method will generate all possible subsequences of length 2 (minimum length) and find if we have already seen that subsequence with the found subsequence. If the subsequence already exists, we return true and terminate the program; otherwise, after completing the iteration, if we found nothing, we return false.

In the worst case, this subsequence may not exist and we end up generating all possible results.

Modified longest common subsequence (LCS)

LCS algorithm finds the longest common subsequence in 2 strings. It is a standard dynamic programming method that uses an iterative method of two-dimensional matrices. The time complexity is O(n^2). We will only search the given string itself in the modified method. Nonetheless, we will also check if the index of the current position is not the same.

Example

See the C code below to implement the modified longest common subsequence algorithm that facilitates our method to find repeating subsequences of length 2 or more -

#include <iostream>
using namespace std;
bool modifiedLongestCommonSubsequence(string s) {
   int n = s.length();
   int dp[n+1][n+1];
   for (int i=0; i<=n; i++)
      fill(dp[i], dp[i]+n+1, 0);
   for (int i=1; i<=n; i++) {
      for (int j=1; j<=n; j++) {
         if (s[i-1]==s[j-1] && i!=j) {
            dp[i][j] = 1 + dp[i-1][j-1];
         }
         else {
            dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
         }
      }
   }
   if(dp[n][n] > 1) return true;
   return false;
}
int main() {
   string str = "PNDPNSP";
   cout << "Repeated subsequence of length 2 or more: " << (modifiedLongestCommonSubsequence(str) ? "Yes" : "No");
   return 0;
}

Output

Repeated subsequence of length 2 or more: Yes

Of course, the time and space complexity is O(n^2), but from the first method, it is more elegant and easy to produce O(1) hash.

Improved solution

In this approach we will try to make some observations based on the previous approach.

Observation 1 − If a character appears more than twice, the answer is always true. Let's see why?

Example - In the string str = "AVHJFBABVNHFA" we have "AAA" in positions 0, 6 and 12. so We can have "AA" at index 0 and 6 as a subsequence, and "AA" at index 6 and 12 as a subsequence as another.

Observation 2 - If a character is repeated only once, it cannot contribute to our results subsequence, since it will only be available in at most one subsequence. it won't work Because we need at least two subsequences. So we can remove or ignore all characters happened at the same time.

Observation 3 − If a string is a palindrome, and the first two observations apply, then the answer is Always false unless the string length is odd. Let's see why?

Example - String str = "PNDDNP"

Explanation - Now, the characters are not in order, so we can never find The subsequences have the same order, so this is not possible.

Example

Based on all three observations above, we conclude that if we remove all characters that appear once in the string and then check if a certain character appears more than twice or if the string is not a palindrome, then we The answer is correct. Let’s see the improved solution implemented in C -

#include <iostream>
using namespace std;
bool isPalindrome(string s) {
   for(int i=0;i<s.size()/2;i++) {
      if(s[i]!=s[s.size()-1-i]) {
         return false;
      }
   }
   return true;
}
bool check(string s) {
   int hash[26] = {0};
   for (int i = 0; i < s.size(); i++) {
      hash[s[i]-'a']++;
      if (hash[s[i]-'a'] > 2) {
         return true;
      }
   }
   int k = 0;
   string mstr = "";
   for (int i = 0; i < s.size(); i++) {
      if (hash[s[i]-'a'] > 1) {
         mstr[k++] = s[i];
      }
   }
   if (isPalindrome(mstr)) {
      return false;
   }
   return true;
}
int main() {
   string s = "PNDPNSP";
   cout << "Repeated subsequence of length 2 or more: " << (check(s) ? "Yes" : "No");
   return 0;
}

Output

Repeated subsequence of length 2 or more: Yes

in conclusion

We concluded that using observations and hashes is the best way to solve this problem. The time complexity is O(n). Space complexity is also on the order of O(n), creating a new string and a constant 26 character hash.

The above is the detailed content of C++ program to find if a given string has a repeating subsequence of length 2 or more. For more information, please follow other related articles on the PHP Chinese website!