Dada una string S , la tarea es contar la máxima ocurrencia de subsecuencias en la string dada de modo que los índices de los caracteres de la subsecuencia sean Progresión aritmética .
Ejemplos:
Entrada: S = “xxxyy”
Salida: 6
Explicación:
Existe una subsecuencia “xy”, donde los índices de cada carácter de la subsecuencia están en AP
Los índices de los diferentes caracteres que forman la subsecuencia “xy” –
{(1, 4 ), (1, 5), (2, 4), (2, 5), (3, 4), (3, 5)}Entrada: S = “pop”
Salida: 2
Explicación:
Existe una subsecuencia “p”, donde los índices de cada carácter de la subsecuencia están en AP
Los índices de los diferentes caracteres que forman la subsecuencia “p” –
{(1), (2)}
Enfoque: La observación clave en el problema es que si hay dos caracteres en una string cuya ocurrencia colectiva es mayor que la ocurrencia de cualquier carácter único, entonces estos caracteres formarán la subsecuencia de ocurrencia máxima en la string con el carácter en Progresión aritmética porque cada dos enteros siempre formarán una progresión aritmética. A continuación se muestra una ilustración de los pasos:
- Iterar sobre la string y contar la frecuencia de los caracteres de la string. Eso es considerando las subsecuencias de longitud 1.
- Iterar sobre la string y elegir cada dos caracteres posibles de la string e incrementar la frecuencia de la subsecuencia de la string.
- Finalmente, encuentre la frecuencia máxima de la subsecuencia de las longitudes 1 y 2.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// maximum occurrence 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 occurrence 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 occurrence of the subsequence
// such that the indices of characters
// are in arithmetic progression
import java.util.*;
class GFG
{
// Function to find the
// maximum occurrence 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 occurrence of the subsequence
# such that the indices of characters
# are in arithmetic progression
# Function to find the
# maximum occurrence 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 occurrence 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 occurrence 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
Javascript
<script>
// Javascript implementation to find the
// maximum occurrence of the subsequence
// such that the indices of characters
// are in arithmetic progression
// Function to find the
// maximum occurrence of the subsequence
// such that the indices of characters
// are in arithmetic progression
function maximumOccurrence(s)
{
var n = s.length;
// Frequencies of subsequence
var freq = new Map();
// Loop to find the frequencies
// of subsequence of length 1
for (var i = 0; i < n; i++) {
var temp = "";
temp += s[i];
if(freq.has(temp))
freq.set(temp, freq.get(temp)+1)
else
freq.set(temp, 1)
}
// Loop to find the frequencies
// subsequence of length 2
for (var i = 0; i < n; i++) {
for (var j = i + 1; j < n; j++) {
var temp = "";
temp += s[i];
temp += s[j];
if(freq.has(temp))
freq.set(temp, freq.get(temp)+1)
else
freq.set(temp, 1)
}
}
var answer = -1000000000;
// Finding maximum frequency
freq.forEach((value, key) => {
answer = Math.max(answer, value);
});
return answer;
}
// Driver Code
var s = "xxxyy";
document.write( maximumOccurrence(s));
</script>
Producción:
6
Complejidad temporal: O(N 2 )
Enfoque eficiente: la idea es utilizar el paradigma de programación dinámica para calcular la frecuencia de las subsecuencias de longitudes 1 y 2 en la string. A continuación se muestra una ilustración de los pasos:
- Calcule la frecuencia de los caracteres de la string en una array de frecuencia.
- Para subsecuencias de la string de longitud 2, el estado DP será
dp[i][j] = Total number of times ith character occurred before jth character.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// maximum occurrence 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 occurrence 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 occurrence
// 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 occurrence of subsequence
// of length 1 in given string
for (int i = 0; i < 26; i++)
answer = max(answer, freq[i]);
// Maximum occurrence 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 occurrence of the subsequence
// such that the indices of characters
// are in arithmetic progression
class GFG{
// Function to find the
// maximum occurrence 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 occurrence
// 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 occurrence of subsequence
// of length 1 in given String
for (int i = 0; i < 26; i++)
answer = Math.max(answer, freq[i]);
// Maximum occurrence 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 occurrence of the subsequence
# such that the indices of characters
# are in arithmetic progression
import sys
# Function to find the maximum occurrence
# 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 occurrence
# of ith character before jth
# character in the given String
for i in range(n):
c = (ord(s[i]) - ord('a'))
for j in range(26):
dp[j] += freq[j]
# Increase the frequency
# of s[i] or c of String
freq += 1
answer = -sys.maxsize
# Maximum occurrence of subsequence
# of length 1 in given String
for i in range(26):
answer = max(answer, freq[i])
# Maximum occurrence of subsequence
# of length 2 in given String
for i in range(26):
for j in range(26):
answer = max(answer, dp[i][j])
return answer
# Driver Code
if __name__ == '__main__':
s = "xxxyy"
print(maximumOccurrence(s))
# This code is contributed by Princi Singh
C#
// C# implementation to find the
// maximum occurrence of the subsequence
// such that the indices of characters
// are in arithmetic progression
using System;
class GFG{
// Function to find the maximum
// occurrence 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 occurrence
// of ith character before jth
// character in the given String
for(int i = 0; i < n; i++)
{
int x = (s[i] - 'a');
for(int j = 0; j < 26; j++)
dp[x, j] += freq[j];
// Increase the frequency
// of s[i] or c of String
freq[x]++;
}
int answer = int.MinValue;
// Maximum occurrence of subsequence
// of length 1 in given String
for(int i = 0; i < 26; i++)
answer = Math.Max(answer, freq[i]);
// Maximum occurrence 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";
Console.Write(maximumOccurrence(s));
}
}
// This code is contributed by Yash_R
Javascript
<script>
// javascript implementation to find the
// maximum occurrence of the subsequence
// such that the indices of characters
// are in arithmetic progression
// Function to find the
// maximum occurrence of the subsequence
// such that the indices of characters
// are in arithmetic progression
function maximumOccurrence(s) {
var n = s.length;
// Frequency for characters
var freq = Array(26).fill(0);
var dp = Array(26).fill().map(()=>Array(26).fill(0));
// Loop to count the occurrence
// of ith character before jth
// character in the given String
for (var i = 0; i < n; i++) {
var c = (s.charCodeAt(i) - 'a'.charCodeAt(0));
for (var j = 0; j < 26; j++)
dp[j] += freq[j];
// Increase the frequency
// of s[i] or c of String
freq++;
}
var answer = Number.MIN_VALUE;
// Maximum occurrence of subsequence
// of length 1 in given String
for (var i = 0; i < 26; i++)
answer = Math.max(answer, freq[i]);
// Maximum occurrence of subsequence
// of length 2 in given String
for (var i = 0; i < 26; i++) {
for (var j = 0; j < 26; j++) {
answer = Math.max(answer, dp[i][j]);
}
}
return answer;
}
// Driver Code
var s = "xxxyy";
document.write(maximumOccurrence(s));
// This code contributed by Princi Singh
</script>
Producción:
6
Complejidad del tiempo: O(26 * N)