Dada una string S que consta de letras minúsculas de tamaño N , la tarea es contar todas las substrings que contienen el carácter más frecuente de la string como primer carácter.
Nota: Si más de un carácter tiene una frecuencia máxima, considere el lexicográficamente más pequeño entre ellos.
Ejemplos:
Entrada: S = “abcab”
Salida: 7
Explicación:
Hay dos caracteres ayb que aparecen un máximo de veces, es decir, 2 veces.
Seleccionar el carácter lexicográficamente más pequeño, es decir, ‘a’.
Las substrings que comienzan con ‘a’ son: “a”, “ab”, “abc”, “abca”, “abcab”, “a”, “ab”.
Por lo tanto, la cuenta es 7.Entrada: S= “cccc”
Salida : 10
Enfoque: la idea es encontrar primero el carácter que aparece la mayor cantidad de veces y luego contar la substring que comienza con ese carácter en la string. Siga los pasos a continuación para resolver el problema:
- Inicialice el conteo como 0 que almacenará el conteo total de strings.
- Encuentre el carácter máximo que aparece en la string S . Que ese personaje sea ch .
- Recorra la string usando la variable i y si el carácter en el i- ésimo índice es el mismo que ch , incremente el conteo en (N – i) .
- Después de los pasos anteriores, imprima el valor de count como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include<bits/stdc++.h>
using namespace std;
// Function to find all substrings
// whose first character occurs
// maximum number of times
int substringCount(string s)
{
// Stores frequency of characters
vector<int> freq(26, 0);
// Stores character that appears
// maximum number of times
char max_char = '#';
// Stores max frequency of character
int maxfreq = INT_MIN;
// Updates frequency of characters
for(int i = 0; i < s.size(); i++)
{
freq[s[i] - 'a']++;
// Update maxfreq
if (maxfreq < freq[s[i] - 'a'])
maxfreq = freq[s[i] - 'a'];
}
// Character that occurs
// maximum number of times
for(int i = 0; i < 26; i++)
{
// Update the maximum frequency
// character
if (maxfreq == freq[i])
{
max_char = (char)(i + 'a');
break;
}
}
// Stores all count of substrings
int ans = 0;
// Traverse over string
for(int i = 0; i < s.size(); i++)
{
// Get the current character
char ch = s[i];
// Update count of substrings
if (max_char == ch)
{
ans += (s.size() - i);
}
}
// Return the count of all
// valid substrings
return ans;
}
// Driver Code
int main()
{
string S = "abcab";
// Function Call
cout << (substringCount(S));
}
// This code is contributed by mohit kumar 29
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to find all substrings
// whose first character occurs
// maximum number of times
static int substringCount(String s)
{
// Stores frequency of characters
int[] freq = new int[26];
// Stores character that appears
// maximum number of times
char max_char = '#';
// Stores max frequency of character
int maxfreq = Integer.MIN_VALUE;
// Updates frequency of characters
for (int i = 0;
i < s.length(); i++) {
freq[s.charAt(i) - 'a']++;
// Update maxfreq
if (maxfreq
< freq[s.charAt(i) - 'a'])
maxfreq
= freq[s.charAt(i) - 'a'];
}
// Character that occurs
// maximum number of times
for (int i = 0; i < 26; i++) {
// Update the maximum frequency
// character
if (maxfreq == freq[i]) {
max_char = (char)(i + 'a');
break;
}
}
// Stores all count of substrings
int ans = 0;
// Traverse over string
for (int i = 0;
i < s.length(); i++) {
// Get the current character
char ch = s.charAt(i);
// Update count of substrings
if (max_char == ch) {
ans += (s.length() - i);
}
}
// Return the count of all
// valid substrings
return ans;
}
// Driver Code
public static void main(String[] args)
{
String S = "abcab";
// Function Call
System.out.println(substringCount(S));
}
}
Python3
# Python3 program for the above approach
import sys
# Function to find all substrings
# whose first character occurs
# maximum number of times
def substringCount(s):
# Stores frequency of characters
freq = [0 for i in range(26)]
# Stores character that appears
# maximum number of times
max_char = '#'
# Stores max frequency of character
maxfreq = -sys.maxsize - 1
# Updates frequency of characters
for i in range(len(s)):
freq[ord(s[i]) - ord('a')] += 1
# Update maxfreq
if (maxfreq < freq[ord(s[i]) - ord('a')]):
maxfreq = freq[ord(s[i]) - ord('a')]
# Character that occurs
# maximum number of times
for i in range(26):
# Update the maximum frequency
# character
if (maxfreq == freq[i]):
max_char = chr(i + ord('a'))
break
# Stores all count of substrings
ans = 0
# Traverse over string
for i in range(len(s)):
# Get the current character
ch = s[i]
# Update count of substrings
if (max_char == ch):
ans += (len(s) - i)
# Return the count of all
# valid substrings
return ans
# Driver Code
if __name__ == '__main__':
S = "abcab"
# Function Call
print(substringCount(S))
# This code is contributed by ipg2016107
C#
// C# program for the above approach
using System;
class GFG{
// Function to find all substrings
// whose first character occurs
// maximum number of times
static int substringCount(string s)
{
// Stores frequency of characters
int[] freq = new int[26];
// Stores character that appears
// maximum number of times
char max_char = '#';
// Stores max frequency of character
int maxfreq = Int32.MinValue;
// Updates frequency of characters
for(int i = 0; i < s.Length; i++)
{
freq[s[i] - 'a']++;
// Update maxfreq
if (maxfreq < freq[s[i] - 'a'])
maxfreq = freq[s[i] - 'a'];
}
// Character that occurs
// maximum number of times
for(int i = 0; i < 26; i++)
{
// Update the maximum frequency
// character
if (maxfreq == freq[i])
{
max_char = (char)(i + 'a');
break;
}
}
// Stores all count of substrings
int ans = 0;
// Traverse over string
for(int i = 0; i < s.Length; i++)
{
// Get the current character
char ch = s[i];
// Update count of substrings
if (max_char == ch)
{
ans += (s.Length - i);
}
}
// Return the count of all
// valid substrings
return ans;
}
// Driver Code
public static void Main()
{
string S = "abcab";
// Function Call
Console.WriteLine(substringCount(S));
}
}
// This code is contributed by susmitakundugoaldanga
Javascript
<script>
// JavaScript program for the above approach
// Function to find all substrings
// whose first character occurs
// maximum number of times
function substringCount(s)
{
// Stores frequency of characters
var freq = new Array(26).fill(0);
// Stores character that appears
// maximum number of times
var max_char = "#";
// Stores max frequency of character
var maxfreq = -21474836487;
// Updates frequency of characters
for(var i = 0; i < s.length; i++)
{
freq[s[i].charCodeAt(0) -
"a".charCodeAt(0)]++;
// Update maxfreq
if (maxfreq < freq[s[i].charCodeAt(0) -
"a".charCodeAt(0)])
maxfreq = freq[s[i].charCodeAt(0) -
"a".charCodeAt(0)];
}
// Character that occurs
// maximum number of times
for(var i = 0; i < 26; i++)
{
// Update the maximum frequency
// character
if (maxfreq === freq[i])
{
max_char = String.fromCharCode(
i + "a".charCodeAt(0));
break;
}
}
// Stores all count of substrings
var ans = 0;
// Traverse over string
for(var i = 0; i < s.length; i++)
{
// Get the current character
var ch = s[i];
// Update count of substrings
if (max_char === ch)
{
ans += s.length - i;
}
}
// Return the count of all
// valid substrings
return ans;
}
// Driver Code
var S = "abcab";
// Function Call
document.write(substringCount(S));
// This code is contributed by rdtank
</script>
Producción:
7
Complejidad de tiempo: O (N), ya que estamos usando un bucle para atravesar la string.
Espacio auxiliar: O (26), ya que estamos usando una array de frecuencias de tamaño 26.