Подсчитайте максимальное количество вхождений подпоследовательности в строке так, чтобы индексы в подпоследовательности находились в AP
Для данной строки S задача состоит в том, чтобы подсчитать максимальное количество вхождений подпоследовательности в данной строке так, чтобы индексы символов подпоследовательности находились в арифметической прогрессии.
Примеры:
Input: S = “xxxyy”
Output: 6
Explanation:
There is a subsequence “xy”, where indices of each character of the subsequence are in A.P.
The indices of the different characters that form the subsequence “xy” –
{(1, 4), (1, 5), (2, 4), (2, 5), (3, 4), (3, 5)}Input: S = “pop”
Output: 2
Explanation:
There is a subsequence “p”, where indices of each character of the subsequence are in A.P.
The indices of the different characters that form the subsequence “p” –
{(1), (2)}
Подход: ключевое наблюдение в проблеме заключается в том, что если в строке есть два символа, совокупное количество которых превышает количество вхождений любого отдельного символа, то эти символы образуют подпоследовательность с максимальным количеством вхождений в строке с символом в арифметической прогрессии из-за каждые два целых числа всегда образуют арифметическую прогрессию. Ниже представлена иллюстрация шагов:
- Обходите строку и подсчитайте частоту символов строки. Это с учетом подпоследовательностей длины 1.
- Перебирайте строку и выбирайте каждые два возможных символа строки и увеличивайте частоту подпоследовательности строки.
- Наконец, найдите максимальную частоту подпоследовательности длины 1 и 2.
Below is the implementation of the above approach:
C++
// C++ implementation to find the // maximum occurence of the subsequence // such that the indices of characters // are in arithmetic progression #include <bits/stdc++.h> using namespace std; // Function to find the // maximum occurence of the subsequence // such that the indices of characters // are in arithmetic progression int maximumOccurrence(string s) { int n = s.length(); // Frequencies of subsequence map<string, int > freq; // Loop to find the frequencies // of subsequence of length 1 for ( int i = 0; i < n; i++) { string temp = "" ; temp += s[i]; freq[temp]++; } // Loop to find the frequencies // subsequence of length 2 for ( int i = 0; i < n; i++) { for ( int j = i + 1; j < n; j++) { string temp = "" ; temp += s[i]; temp += s[j]; freq[temp]++; } } int answer = INT_MIN; // Finding maximum frequency for ( auto it : freq) answer = max(answer, it.second); return answer; } // Driver Code int main() { string s = "xxxyy" ; cout << maximumOccurrence(s); return 0; } |
Java
// Java implementation to find the // maximum occurence of the subsequence // such that the indices of characters // are in arithmetic progression import java.util.*; class GFG { // Function to find the // maximum occurence of the subsequence // such that the indices of characters // are in arithmetic progression static int maximumOccurrence(String s) { int n = s.length(); // Frequencies of subsequence HashMap<String, Integer> freq = new HashMap<String,Integer>(); int i, j; // Loop to find the frequencies // of subsequence of length 1 for ( i = 0 ; i < n; i++) { String temp = "" ; temp += s.charAt(i); if (freq.containsKey(temp)){ freq.put(temp,freq.get(temp)+ 1 ); } else { freq.put(temp, 1 ); } } // Loop to find the frequencies // subsequence of length 2 for (i = 0 ; i < n; i++) { for (j = i + 1 ; j < n; j++) { String temp = "" ; temp += s.charAt(i); temp += s.charAt(j); if (freq.containsKey(temp)) freq.put(temp,freq.get(temp)+ 1 ); else freq.put(temp, 1 ); } } int answer = Integer.MIN_VALUE; // Finding maximum frequency for ( int it : freq.values()) answer = Math.max(answer, it); return answer; } // Driver Code public static void main(String []args) { String s = "xxxyy" ; System.out.print(maximumOccurrence(s)); } } // This code is contributed by chitranayal |
Python3
# Python3 implementation to find the # maximum occurence of the subsequence # such that the indices of characters # are in arithmetic progression # Function to find the # maximum occurence of the subsequence # such that the indices of characters # are in arithmetic progression def maximumOccurrence(s): n = len (s) # Frequencies of subsequence freq = {} # Loop to find the frequencies # of subsequence of length 1 for i in s: temp = "" temp + = i freq[temp] = freq.get(temp, 0 ) + 1 # Loop to find the frequencies # subsequence of length 2 for i in range (n): for j in range (i + 1 , n): temp = "" temp + = s[i] temp + = s[j] freq[temp] = freq.get(temp, 0 ) + 1 answer = - 10 * * 9 # Finding maximum frequency for it in freq: answer = max (answer, freq[it]) return answer # Driver Code if __name__ = = "__main__" : s = "xxxyy" print (maximumOccurrence(s)) # This code is contributed by mohit kumar 29 |
C#
// C# implementation to find the // maximum occurence of the subsequence // such that the indices of characters // are in arithmetic progression using System; using System.Collections.Generic; class GFG { // Function to find the // maximum occurence of the subsequence // such that the indices of characters // are in arithmetic progression static int maximumOccurrence( string s) { int n = s.Length; // Frequencies of subsequence Dictionary< string , int > freq = new Dictionary< string , int >(); int i, j; // Loop to find the frequencies // of subsequence of length 1 for ( i = 0; i < n; i++) { string temp = "" ; temp += s[i]; if (freq.ContainsKey(temp)) { freq[temp]++; } else { freq[temp] = 1; } } // Loop to find the frequencies // subsequence of length 2 for (i = 0; i < n; i++) { for (j = i + 1; j < n; j++) { string temp = "" ; temp += s[i]; temp += s[j]; if (freq.ContainsKey(temp)) freq[temp]++; else freq[temp] = 1; } } int answer = int .MinValue; // Finding maximum frequency foreach (KeyValuePair< string , int > it in freq) answer = Math.Max(answer, it.Value); return answer; } // Driver Code public static void Main( string []args) { string s = "xxxyy" ; Console.Write(maximumOccurrence(s)); } } // This code is contributed by Rutvik_56 |
6
Сложность времени: O (N 2 )
Эффективный подход: идея состоит в том, чтобы использовать парадигму динамического программирования для вычисления частоты подпоследовательностей длины 1 и 2 в строке. Ниже представлена иллюстрация шагов:
- Вычислите частоту символов строки в частотном массиве.
- Для подпоследовательностей строки длиной 2 состояние DP будет
dp [i] [j] = Общее количество раз i th символ встречается до j- го символа.
Below is the implementation of the above approach:
C++
// C++ implementation to find the // maximum occurence of the subsequence // such that the indices of characters // are in arithmetic progression #include <bits/stdc++.h> using namespace std; // Function to find the // maximum occurence of the subsequence // such that the indices of characters // are in arithmetic progression int maximumOccurrence(string s) { int n = s.length(); // Frequency for characters int freq[26] = { 0 }; int dp[26][26] = { 0 }; // Loop to count the occurence // of ith character before jth // character in the given string for ( int i = 0; i < n; i++) { int c = (s[i] - "a" ); for ( int j = 0; j < 26; j++) dp[j] += freq[j]; // Increase the frequency // of s[i] or c of string freq++; } int answer = INT_MIN; // Maximum occurence of subsequence // of length 1 in given string for ( int i = 0; i < 26; i++) answer = max(answer, freq[i]); // Maximum occurence of subsequence // of length 2 in given string for ( int i = 0; i < 26; i++) { for ( int j = 0; j < 26; j++) { answer = max(answer, dp[i][j]); } } return answer; } // Driver Code int main() { string s = "xxxyy" ; cout << maximumOccurrence(s); return 0; } |
Java
// Java implementation to find the // maximum occurence of the subsequence // such that the indices of characters // are in arithmetic progression class GFG{ // Function to find the // maximum occurence of the subsequence // such that the indices of characters // are in arithmetic progression static int maximumOccurrence(String s) { int n = s.length(); // Frequency for characters int freq[] = new int [ 26 ]; int dp[][] = new int [ 26 ][ 26 ]; // Loop to count the occurence // of ith character before jth // character in the given String for ( int i = 0 ; i < n; i++) { int c = (s.charAt(i) - "a" ); for ( int j = 0 ; j < 26 ; j++) dp[j] += freq[j]; // Increase the frequency // of s[i] or c of String freq++; } int answer = Integer.MIN_VALUE; // Maximum occurence of subsequence // of length 1 in given String for ( int i = 0 ; i < 26 ; i++) answer = Math.max(answer, freq[i]); // Maximum occurence of subsequence // of length 2 in given String for ( int i = 0 ; i < 26 ; i++) { for ( int j = 0 ; j < 26 ; j++) { answer = Math.max(answer, dp[i][j]); } } return answer; } // Driver Code public static void main(String[] args) { String s = "xxxyy" ; System.out.print(maximumOccurrence(s)); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 implementation to find the # maximum occurence of the subsequence # such that the indices of characters # are in arithmetic progression import sys # Function to find the maximum occurence # of the subsequence such that the # indices of characters are in # arithmetic progression def maximumOccurrence(s): n = len (s) # Frequency for characters freq = [ 0 ] * ( 26 ) dp = [[ 0 for i in range ( 26 )] for j in range ( 26 )] # Loop to count the occurence # of ith character before jth # character in the given String for i in range (n): c = ( ord (s[i]) - ord ( "a" ))
|