Подсчитайте максимальное количество вхождений подпоследовательности в строке так, чтобы индексы в подпоследовательности находились в AP

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

Для данной строки 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)} 
 

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

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

  • Обходите строку и подсчитайте частоту символов строки. Это с учетом подпоследовательностей длины 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
Output: 
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"))
 
        
Олимпиады по программированию Алгоритмы

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

Разница между жадным алгоритмом и алгоритмом «разделяй и властвуй»
14 Февраля, 2023
Сжатие и распаковка текстовых файлов с использованием кодирования Хаффмана
21 Января, 2023
Введение в амортизированный анализ
12 Января, 2023
Как анализировать сложность рекуррентного отношения
12 Января, 2023
Настройка Sublime Text для соревновательного программирования (C++) с использованием плагина Fast Olympic Coding
8 Января, 2023
Наихудший, средний и лучший анализ алгоритмов
4 Января, 2023
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Что такое логарифмическая временная сложность? Полное руководство
12 Декабря, 2022