Given a string, the task is to check if there exist two equal sub-sequences in the given string. Two sub-sequences are said to be equal if they have the same characters arranged in the same lexicographical order but the position of characters differs from that in the original string.
Examples:
Input: str = “neveropen”
Output: YES
Two possible sub-sequences are “neveropen” and “neveropen”.
Input: str = “bhuvan”
Output: NO
Approach: The approach to solving this problem is to check if any character appears more than once. Since the minimal length of matching subsequence can be 1, hence if a character occurrence in a string more than once then two similar subsequences is possible. Initialize a freq[] array of length 26. Iterate over the string and increment the frequency of the characters. Iterate over the freq array and check if freq[i] for any i in the range of 0-26 is more than 1, then it is possible.
Below is the implementation of the above approach.
C++
// C++ program to Check if// similar subsequences exist or not#include <bits/stdc++.h>using namespace std;// Function to check if similar subsequences// occur in a string or notbool check(string s, int l){ int freq[26] = { 0 }; // iterate and count the frequency for (int i = 0; i < l; i++) { freq[s[i] - 'a']++; // counting frequency of the letters } // check if frequency is more // than once of any character for (int i = 0; i < 26; i++) { if (freq[i] >= 2) return true; } return false;}// Driver Codeint main(){ string s = "neveropen"; int l = s.length(); if (check(s, l)) cout << "YES"; else cout << "NO"; return 0;} |
Java
// Java program to Check // if similar subsequences // exist or notimport java.io.*;import java.util.*;import java.util.Arrays;class GFG{// Function to check if// similar subsequences// occur in a string or notstatic boolean check(String s, int l){ int freq[] = new int[26]; Arrays.fill(freq, 0); // iterate and count // the frequency for (int i = 0; i < l; i++) { // counting frequency // of the letters freq[s.charAt(i) - 'a']++; } // check if frequency is more // than once of any character for (int i = 0; i < 26; i++) { if (freq[i] >= 2) return true; } return false;}// Driver Codepublic static void main(String args[]){ String s = "neveropen"; int l = s.length(); if (check(s, l)) System.out.print("YES"); else System.out.print("NO");}} |
Python3
# Python 3 program to Check if# similar subsequences exist or not# Function to check if similar subsequences# occur in a string or notdef check(s, l): freq = [0 for i in range(26)] # iterate and count the frequency for i in range(l): # counting frequency of the letters freq[ord(s[i]) - ord('a')] += 1 # check if frequency is more # than once of any character for i in range(26): if (freq[i] >= 2): return True return False# Driver Codeif __name__ == '__main__': s = "neveropen" l = len(s) if (check(s, l)): print("YES") else: print("NO")# This code is contributed by# Sahil_Shelangia |
C#
// C# program to Check if similar subsequences // exist or notusing System;using System.Collections.Generic; class GFG{ // Function to check if similar subsequences// occur in a string or notstatic bool check(String s, int l){ int []freq = new int[26]; // iterate and count the frequency for (int i = 0; i < l; i++) { // counting frequency of the letters freq[s[i] - 'a']++; } // check if frequency is more // than once of any character for (int i = 0; i < 26; i++) { if (freq[i] >= 2) return true; } return false;}// Driver Codepublic static void Main(String []args){ String s = "neveropen"; int l = s.Length; if (check(s, l)) Console.WriteLine("YES"); else Console.WriteLine("NO");}}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// JavaScript program to Check // if similar subsequences // exist or not// Function to check if// similar subsequences// occur in a string or notfunction check(s, l){ let freq = new Array(26).fill(0); // iterate and count // the frequency for (let i = 0; i < l; i++) { // counting frequency // of the letters freq[s[i].charCodeAt() - 'a'.charCodeAt()]++; } // check if frequency is more // than once of any character for (let i = 0; i < 26; i++) { if (freq[i] >= 2) return true; } return false;} // Driver Code let s = "neveropen"; let l = s.length; if (check(s, l)) document.write("YES"); else document.write("NO"); </script> |
YES
Time Complexity: O(N)
Auxiliary Space: O(1)
Note: If the length of a similar subsequence was mentioned, then the approach to solve the problem will also be different. The approach to check if a string contains two repeated subsequences of length two or more is discussed in this post.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
