Check if two same sub-sequences exist in a string or not
Last Updated :
30 May, 2022
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 = “geeksforgeeks”
Output: YES
Two possible sub-sequences are “geeks” and “geeks”.
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++
#include <bits/stdc++.h>
using namespace std;
bool check(string s, int l)
{
int freq[26] = { 0 };
for (int i = 0; i < l; i++) {
freq[s[i] - 'a']++;
}
for (int i = 0; i < 26; i++) {
if (freq[i] >= 2)
return true;
}
return false;
}
int main()
{
string s = "geeksforgeeks";
int l = s.length();
if (check(s, l))
cout << "YES";
else
cout << "NO";
return 0;
}
|
Java
import java.io.*;
import java.util.*;
import java.util.Arrays;
class GFG
{
static boolean check(String s,
int l)
{
int freq[] = new int[26];
Arrays.fill(freq, 0);
for (int i = 0; i < l; i++)
{
freq[s.charAt(i) - 'a']++;
}
for (int i = 0; i < 26; i++)
{
if (freq[i] >= 2)
return true;
}
return false;
}
public static void main(String args[])
{
String s = "geeksforgeeks";
int l = s.length();
if (check(s, l))
System.out.print("YES");
else
System.out.print("NO");
}
}
|
Python3
def check(s, l):
freq = [0 for i in range(26)]
for i in range(l):
freq[ord(s[i]) - ord('a')] += 1
for i in range(26):
if (freq[i] >= 2):
return True
return False
if __name__ == '__main__':
s = "geeksforgeeks"
l = len(s)
if (check(s, l)):
print("YES")
else:
print("NO")
|
C#
using System;
using System.Collections.Generic;
class GFG
{
static bool check(String s, int l)
{
int []freq = new int[26];
for (int i = 0; i < l; i++)
{
freq[s[i] - 'a']++;
}
for (int i = 0; i < 26; i++)
{
if (freq[i] >= 2)
return true;
}
return false;
}
public static void Main(String []args)
{
String s = "geeksforgeeks";
int l = s.Length;
if (check(s, l))
Console.WriteLine("YES");
else
Console.WriteLine("NO");
}
}
|
Javascript
<script>
function check(s, l)
{
let freq = new Array(26).fill(0);
for (let i = 0; i < l; i++)
{
freq[s[i].charCodeAt() - 'a'.charCodeAt()]++;
}
for (let i = 0; i < 26; i++)
{
if (freq[i] >= 2)
return true;
}
return false;
}
let s = "geeksforgeeks";
let l = s.length;
if (check(s, l))
document.write("YES");
else
document.write("NO");
</script>
|
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.
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...