Repeated Subsequence of Length Two or More

Difficulty Level Medium
Frequently asked in Adobe
StringViews 1647

Problem Statement

In the “Repeated Subsequence of Length Two or More” problem we have given the string “s”. Find if there is any subsequence of length two 0r more. The sub-sequences should not have the same character at the same position.

Input Format

The first and only one line containing a string “s”.

Output Format

Print “Yes” if there exist a Repeated Subsequence of Length Two or More which should not have the same character at the same position. Otherwise print “No”.

Constraints

  • 1<=|s|<=10^6
  • s[i] must be a lower case English alphabet

Example

abdabc
Yes

Explanation: Here “ab” is the repeated subsequence which is present in the given string.

ppq
No

Explanation: Here “pq” is the repeated subsequence, but q is at the same positions in both sub-sequences.

Algorithm for Repeated Subsequence of Length Two or More

This problem is classic variation of longest common subsequence problem. Dynamic programming solution takes O(n2) time and space. In this article, O(n) time and space approach is discussed.

  1. We remove all the non-repeated characters from the string.
  2. Create an array to store the frequencies of characters.
  3. Traverse the input string and store the frequencies of all characters in the count array.
  4. If the count of a character is more than 3, return true. (considering conditions like “ppp” which are palindrome but sub-sequence exists.)
  5. We in-place remove all non-repeating characters from the string.
  6. Check if the resultant string is palindrome or not.
  7. If palindrome print “No”. Except if the length is odd return true if the middle character is same as previous one. (“ppp” condition)
  8. Print “Yes”, if the string is not a palindrome.

Implementation

C++ Program for Repeated Subsequence of Length Two or More

#include <bits/stdc++.h> 
#define MAX_CHAR 256 
using namespace std; 

bool isPalindrome(string s, int l, int h) 
{ 
  while (h > l) 
    if (s[l++] != s[h--]) 
      return false; 
  return true; 
} 

int check(string s) 
{  
  int n = s.length(); 
  int freq[256];
  memset(freq,0,sizeof(freq));
  for (int i = 0; i < n; i++) 
  { 
    freq[s[i]]++; 
    if (freq[s[i]] > 2) 
      return true; 
  } 
  int k = 0; 
  for (int i = 0; i < n; i++) 
    if (freq[s[i]] > 1) 
      s[k++] = s[i]; 
  s[k] = '\0'; 
  if(isPalindrome(s, 0, k-1)) 
  { 
    if(k & 1) 
      return s[k/2] == s[k/2 - 1]; 
    return false; 
  } 
  return true; 
} 

int main() 
{ 
  string s;
  cin>>s;
  if(check(s)) 
    cout<<"Yes"<<endl; 
  else
    cout<<"No"<<endl; 
  return 0; 
}

Java Program for Repeated Subsequence of Length Two or More

import java.util.HashMap;
import java.util.Scanner;
class sum
{
    public static int isPalindrome(String s, int l, int h)  
    { 
        while(h > l) 
            if(s.charAt(l++) != s.charAt(h--)) 
                return 0; 
        return 1; 
    }
    
    public static int  check(String s)
    {
        int n = s.length(); 
  int freq[] = new int[256];
        for(int i=0;i<256;i++)
  {
      freq[i]=0;
  }
  for (int i = 0; i < n; i++) 
  { 
    freq[s.charAt(i)]++; 
    if(freq[s.charAt(i)]>2) 
      return 1; 
  } 
  int k = 0;  
        for(int i = 0; i < n; i++)  
            if(freq[s.charAt(i)] > 1)  
                s.replace(s.charAt(k++),  
                            s.charAt(i));  
        s.replace(s.charAt(k), '\0'); 
        if(isPalindrome(s, 0, k - 1)==1)  
        {  
            if ((k & 1) == 1)  
            { 
                if (k / 2 >= 1) 
                    return (s.charAt(k / 2) == s.charAt(k / 2 - 1))? 1: 0; 
            } 
            return 0;  
        }  
        return 1;
    }
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        String s = sr.next();
  if(check(s)!=1)
  {
      System.out.println("No");
  }
  else
  {
      System.out.println("Yes");
  }
    }
}

dwjebkufbfbfewdbfeb
Yes

Complexity Analysis for Repeated Subsequence of Length Two or More

Time Complexity

O(n) where n is the size of the given string “s”. Here we perform some operations in linear time only.

Space Complexity

O(1) because we declare an array of size 256 only which we use to store the freq of each char.

Translate »