Максимальное количество палиндромных подпоследовательностей трех длин с каждой индексной частью одной подпоследовательности

Опубликовано: 3 Января, 2022

Для данной строки S задача состоит в том, чтобы найти максимальное количество различных индексированных палиндромных подпоследовательностей длины 3, возможных из данной строки.

Примеры:

Input: str = “geekforg”
Output: 2
Explanation:Possible palindromic subsequences of length 3 satisfying the conditions are “gkg” and “efe”. Therefore, the required output is 2.
Input: str = “geek”
Output: 1
Explanation: Possible palindromic subsequences of length 3 satisfying the conditions are “ege” .

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: идея состоит в том, чтобы подсчитать частоту каждого символа строки S и подсчитать пары частот так, чтобы пары состояли из одинаковых символов, и подсчитать количество подпоследовательностей длиной 3 , разделив строку S на 3 . Наконец, выведите минимум пар частот как количество подпоследовательностей. Выполните следующие действия, чтобы решить проблему:

Инициализируйте массив, скажем freq [] , для хранения частот каждого символа строки S.
Инициализируйте переменную, скажем freqPair , для хранения пар частот, в которых пары имеют одинаковые символы.
Инициализируйте переменную, например len , для хранения количества подпоследовательностей длины 3 строки S.
Итерировать в диапазоне [0, str.length () - 1] . Для каждого i- ^го индекса строки S увеличьте количество символов freq [S [i] - 'a'] на 1 .
Итерировать в диапазоне [0, 26] . Для каждого i- ^го индекса массива freq [] подсчитайте пары частот, разделив элемент массива на 2 .
Наконец, выведите значение минимума freqPair и len .

Ниже представлена реализация описанного выше подхода:

C ++

 // C++ program to implement
 // the above approach
 #include <bits/stdc++.h>
 using namespace std;
 // Function to count the maximum number
 // oaf palindrome subsequences of length 3
 // considering the same index only once
 int maxNumPalindrome(string S)
 {
    // Index of the string S
    int i = 0; 
    // Stores the frequency of
    // every character
    int freq[26] = { 0 }; 
    // Stores the pair of frequency
    // containing same characters
    int freqPair = 0; 
    // Number of subsequences
    // having length 3
    int len = S.length() / 3; 
    // Counts the frequency
    while (i < S.length()) { 
        freq[S[i] - 'a' ]++;
        i++;
    }
    // Counts the pair of frequency
    for (i = 0; i < 26; i++) { 
        freqPair += (freq[i] / 2);
    }
    // Returns the minimum value
    return min(freqPair, len);
 }
 // Driver Code
 int main()
 {
    string S = "geeksforg" ; 
    cout << maxNumPalindrome(S) << endl;
    return 0;
 }

Джава

 // Java program to implement
 // the above approach
 import java.util.*;
 class GFG {
  
    // Driver Code
    public static void main(String[] args)
    {
        String S = "geeksforg" ; 
        System.out.println(maxNumPalindrome(S));
    }
    // Function to count the maximum number
    // of palindrome subsequences of length 3
    // considering the same index only once
    static int maxNumPalindrome(String S)
    {
        // Index of the string S
        int i = 0 ; 
        // Stores the frequency of
        // every character
        int [] freq = new int [ 26 ]; 
        // Stores the pair of frequency
        // containing same characters
        int freqPair = 0 ; 
        // Number of subsequences
        // having length 3
        int len = S.length() / 3 ; 
        // Counts the frequency
        while (i < S.length()) { 
            freq[S.charAt(i) - 'a' ]++;
            i++;
        }
        // Counts the pair of frequency
        for (i = 0 ; i < 26 ; i++) { 
            freqPair += (freq[i] / 2 );
        }
        // Returns the minimum value
        return Math.min(freqPair, len);
    }
 }

Python3

 # Python3 program to implement
 # the above approach
 # Function to count the maximum number
 # of palindrome subsequences of length 3
 # considering the same index only once
 def maxNumPalindrome(S):
    
    # Index of the S
    i = 0 
    # Stores the frequency of
    # every character
    freq = [ 0 ] * 26 
    # Stores the pair of frequency
    # containing same characters
    freqPair = 0 
    # Number of subsequences
    # having length 3
    ln = len (S) / / 3 
    # Counts the frequency
    while (i < len (S)):
        freq[ ord (S[i]) - ord ( 'a' )] + = 1
        i + = 1 
    # Counts the pair of frequency
    for i in range ( 26 ):
        freqPair + = (freq[i] / / 2 ) 
    # Returns the minimum value
    return min (freqPair, ln)
 # Driver Code
 if __name__ = = '__main__' : 
    S = "geeksforg" 
    print (maxNumPalindrome(S))
 # This code is contributed by mohit kumar 29

C #

 // C# program to implement
 // the above approach
 using System;
 class GFG
 {
  
    // Driver Code
    public static void Main(String[] args)
    {
        string S = "geeksforg" ;
        Console.WriteLine(maxNumPalindrome(S));
    }
    // Function to count the maximum number
    // of palindrome subsequences of length 3
    // considering the same index only once
    static int maxNumPalindrome( string S)
    {
        // Index of the string S
        int i = 0; 
        // Stores the frequency of
        // every character
        int [] freq = new int [26]; 
        // Stores the pair of frequency
        // containing same characters
        int freqPair = 0; 
        // Number of subsequences
        // having length 3
        int len = S.Length / 3; 
        // Counts the frequency
        while (i < S.Length)
        {
            freq[S[i] - 'a' ]++;
            i++;
        }
        // Counts the pair of frequency
        for (i = 0; i < 26; i++)
        {
            freqPair += (freq[i] / 2);
        }
        // Returns the minimum value
        return Math.Min(freqPair, len);
    }
 }
 // This code is contributed by susmitakundugoaldanga.

Выход:

Сложность времени: O (| S | + 26)
Вспомогательное пространство: O (26)

Вниманию читателя! Не прекращайте учиться сейчас. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Technical Scripter

Максимальное количество палиндромных подпоследовательностей трех длин с каждой индексной частью одной подпоследовательности

C ++

Джава

Python3

C #

РЕКОМЕНДУЕМЫЕ СТАТЬИ