检查字符串中是否存在两个相同的子序列-yiteyi-C++库

给定一个字符串，任务是检查给定字符串中是否存在两个相等的子序列。如果两个子序列中的相同字符按相同的词典顺序排列，但字符的位置不同于原始字符串中的位置，则称它们相等。 例如：

null

输入： str=“Geeksforgeks” 输出： 对两个可能的子序列是“极客”和“极客”。 输入： str=“bhuvan” 输出： 不

方法： 解决这个问题的方法是检查是否有任何字符出现不止一次。由于匹配子序列的最小长度可以是1，因此，如果字符串中的字符出现多次，则可能出现两个类似的子序列。初始化 频率[] 长度为26的数组。迭代字符串并增加字符的频率。迭代freq数组，检查0-26范围内任何i的freq[i]是否大于1，那么这是可能的。以下是上述方法的实施情况。

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 not                       
                         bool                                     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 Code                       
                         int                                     main()                       
                         {                       
                                                 string s =                                     "geeksforgeeks"                                     ;                       
                                                 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 not                       
                         import                                     java.io.*;                       
                         import                                     java.util.*;                       
                         import                                     java.util.Arrays;                       
           
                         class                                     GFG                       
                         {                       
                         // Function to check if                       
                         // similar subsequences                       
                         // occur in a string or not                       
                         static                                     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 Code                       
                         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

                         # Python 3 program to Check if                       
                         # similar subsequences exist or not                       
           
                         # Function to check if similar subsequences                       
                         # occur in a string or not                       
                         def                                     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 Code                       
                         if                                     __name__                                     =                                     =                                     '__main__'                                     :                       
                                                 s                                     =                                     "geeksforgeeks"                       
                                                 l                                     =                                     len                                     (s)                       
                                                 if                                     (check(s, l)):                       
                                                 print                                     (                                     "YES"                                     )                       
                                                 else                                     :                       
                                                 print                                     (                                     "NO"                                     )                       
           
                         # This code is contributed by                       
                         # Sahil_Shelangia                       

C#

                         // C# Pprogram to Check if similar subsequences                       
                         // exist or not                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
           
                         class                                     GFG                       
                         {                       
                                   
                         // Function to check if similar subsequences                       
                         // occur in a string or not                       
                         static                                     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 Code                       
                         public                                     static                                     void                                     Main(String []args)                       
                         {                       
                                                 String s =                                     "geeksforgeeks"                                     ;                       
                                                 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 not                       
                         function                                     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 =                                     "geeksforgeeks"                                     ;                       
                                                 let l = s.length;                       
                                                 if                                     (check(s, l))                       
                                                 document.write(                                     "YES"                                     );                       
                                                 else                       
                                                 document.write(                                     "NO"                                     );                       
                                   
                         </script>                       

输出：

YES

时间复杂性： O（N） 辅助空间： O（1）笔记：如果提到类似子序列的长度，那么解决问题的方法也将不同。中讨论了检查字符串是否包含长度为两个或两个以上的重复子序列的方法这邮递

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章