Dada una string S que consta de caracteres de ‘a’ a ‘z’. La tarea es encontrar la longitud de la substring más grande de S que contiene un carácter cuya frecuencia en la substring es mayor o igual a la mitad de la longitud de la substring.
Nota : para substrings de longitud impar, para calcular la longitud media, considere la división de enteros. Por ejemplo, la mitad de 11 es 5.
Ejemplos:
Input : S = "ababbbacbcbcca" Output : 13 Substring from index 1(0-based indexing) to index 13, "babbbacbcbcca" have b's frequency equals to 6 which is equal to half of the length of substring (13/2 = 6). Input : S = "abcde" Output : 3
Enfoque simple : la idea es encontrar toda la substring de S y, para cada substring, encontrar la frecuencia de cada carácter y compararla con la mitad de la longitud de la substring. Ahora, entre todas las substrings que satisfacen la condición, la salida es la longitud de la que tiene la mayor longitud.
Enfoque eficiente :
Primero, observe que solo puede haber 26 caracteres distintos en la string S. Entonces, considere cada carácter uno por uno por tener una frecuencia mayor o igual a la longitud de la substring.
Entonces, para encontrar la longitud de la substring más larga posible que satisfaga la condición, para cada carácter crearemos la array de prefijos del conteo del carácter. Por ejemplo, para S = “abacdaef”, la array de prefijos para ‘a’ será, por ejemplo, freq[] , [1, 1, 2, 2, 2, 3, 3, 3].
Estamos buscando las siguientes condiciones para satisfacer:
freq[r] - freq[l - 1] >= (r - l)/2, where l, r are the indices.
Además, podemos escribir,
(2 * freq[r]) - r >= (2 * freq[l - 1]) - l
Entonces, encuentra dos arreglos r[] y l[] , donde r[i] = (2 * freq[i]) – i y l[i] = (2 * freq[l – 1]) – l, para 1 <= i <= longitud de S.
Ahora, para cada i en r[] , encuentre el límite inferior en l[] usando una búsqueda binaria tal que el índice sea mínimo en l[], digamos j.
Entonces, i – j + 1 es una de las soluciones. Encuentre el máximo.
Luego repite el método anterior para cada carácter.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the length of the longest
// sub string having frequency of a character
// greater than half of the length of the
// sub string
int maxLength(string s, int n)
{
int ans = INT_MIN;
vector<int> A, L, R;
int freq[n + 5];
// for each of the character 'a' to 'z'
for (int i = 0; i < 26; i++) {
int count = 0;
memset(freq, 0, sizeof freq);
// finding frequency prefix array of the
// character
for (int j = 0; j < n; j++) {
if (s[j] - 'a' == i)
count++;
freq[j] = count;
}
// Finding the r[] and l[] arrays.
for (int j = 0; j < n; j++) {
L.push_back((2 * freq[j - 1]) - j);
R.push_back((2 * freq[j]) - j);
}
int max_len = INT_MIN;
int min_val = INT_MAX;
// for each j from 0 to n
for (int j = 0; j < n; j++) {
min_val = min(min_val, L[j]);
A.push_back(min_val);
int l = 0, r = j;
// Finding the lower bound of i.
while (l <= r) {
int mid = (l + r) >> 1;
if (A[mid] <= R[j]) {
max_len = max(max_len, j - mid + 1);
r = mid - 1;
}
else {
l = mid + 1;
}
}
}
// storing the maximum value of i - j + 1
ans = max(ans, max_len);
// clearing all the vector so that it clearing
// be use for other character.
A.clear();
R.clear();
L.clear();
}
return ans;
}
// Driver Code
int main()
{
string s = "ababbbacbcbcca";
int n = s.length();
cout << maxLength(s, n) << '\n';
return 0;
}
Java
// Java implementation of the above approach
import java.util.*;
class GFG
{
// Function to return the length of the longest
// sub string having frequency of a character
// greater than half of the length of the
// sub string
static int maxLength(String s, int n)
{
int ans = Integer.MIN_VALUE;
Vector<Integer> A = new Vector<Integer>();
Vector<Integer> L = new Vector<Integer>();
Vector<Integer> R = new Vector<Integer>();
int []freq = new int[n + 5];
// for each of the character 'a' to 'z'
for (int i = 0; i < 26; i++)
{
int count = 0;
// finding frequency prefix array of the
// character
for (int j = 0; j < n; j++)
{
if (s.charAt(j) - 'a' == i)
count++;
freq[j] = count;
}
// Finding the r[] and l[] arrays.
for (int j = 1; j < n; j++)
{
L.add((2 * freq[j - 1]) - j);
R.add((2 * freq[j]) - j);
}
int max_len = Integer.MIN_VALUE;
int min_val = Integer.MAX_VALUE;
// for each j from 0 to n
for (int j = 0; j < L.size(); j++)
{
min_val = Math.min(min_val, L.get(j));
A.add(min_val);
int l = 0, r = j;
// Finding the lower bound of i.
while (l <= r)
{
int mid = (l + r) >> 1;
if (A.get(mid) <= R.get(j))
{
max_len = Math.max(max_len,
j - mid + 1);
r = mid - 1;
}
else
{
l = mid + 1;
}
}
}
// storing the maximum value of i - j + 1
ans = Math.max(ans, max_len);
// clearing all the vector so that it clearing
// be use for other character.
A.clear();
R.clear();
L.clear();
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
String s = "ababbbacbcbcca";
int n = s.length();
System.out.println(maxLength(s, n));
}
}
// This code is contributed by Princi Singh
Python3
# Python3 implementation of the above approach
import sys
# Function to return the length
# of the longest sub string
# having frequency of a character
# greater than half of the length
# of the sub string
def maxLength(s, n) :
ans = -(sys.maxsize + 1);
A, L, R = [], [], [];
freq = [0] * (n + 5);
# for each of the character 'a' to 'z'
for i in range(26) :
count = 0;
# finding frequency prefix array
# of the character
for j in range(n) :
if (ord(s[j]) - ord('a') == i) :
count += 1;
freq[j] = count;
# Finding the r[] and l[] arrays.
for j in range(n) :
L.append((2 * freq[j - 1]) - j);
R.append((2 * freq[j]) - j);
max_len = -(sys.maxsize + 1);
min_val = sys.maxsize ;
# for each j from 0 to n
for j in range(n) :
min_val = min(min_val, L[j]);
A.append(min_val);
l = 0; r = j;
# Finding the lower bound of i.
while (l <= r) :
mid = (l + r) >> 1;
if (A[mid] <= R[j]) :
max_len = max(max_len, j - mid + 1);
r = mid - 1;
else :
l = mid + 1;
# storing the maximum value of i - j + 1
ans = max(ans, max_len);
# clearing all the vector so that it can
# be used for other characters.
A.clear();
R.clear();
L.clear();
return ans;
# Driver Code
if __name__ == "__main__" :
s = "ababbbacbcbcca";
n = len(s);
print(maxLength(s, n));
# This code is contributed by AnkitRai01
C#
// C# implementation of the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to return the length of the longest
// sub string having frequency of a character
// greater than half of the length of the
// sub string
static int maxLength(String s, int n)
{
int ans = int.MinValue;
List<int> A = new List<int>();
List<int> L = new List<int>();
List<int> R = new List<int>();
int []freq = new int[n + 5];
// for each of the character 'a' to 'z'
for (int i = 0; i < 26; i++)
{
int count = 0;
// finding frequency prefix array of the
// character
for (int j = 0; j < n; j++)
{
if (s[j] - 'a' == i)
count++;
freq[j] = count;
}
// Finding the r[] and l[] arrays.
for (int j = 1; j < n; j++)
{
L.Add((2 * freq[j - 1]) - j);
R.Add((2 * freq[j]) - j);
}
int max_len = int.MinValue;
int min_val = int.MaxValue;
// for each j from 0 to n
for (int j = 0; j < L.Count; j++)
{
min_val = Math.Min(min_val, L[j]);
A.Add(min_val);
int l = 0, r = j;
// Finding the lower bound of i.
while (l <= r)
{
int mid = (l + r) >> 1;
if (A[mid] <= R[j])
{
max_len = Math.Max(max_len,
j - mid + 1);
r = mid - 1;
}
else
{
l = mid + 1;
}
}
}
// storing the maximum value of i - j + 1
ans = Math.Max(ans, max_len);
// clearing all the vector so that it can
// be used for other characters.
A.Clear();
R.Clear();
L.Clear();
}
return ans;
}
// Driver Code
public static void Main(String[] args)
{
String s = "ababbbacbcbcca";
int n = s.Length;
Console.WriteLine(maxLength(s, n));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript implementation of the above approach
// Function to return the length of the longest
// sub string having frequency of a character
// greater than half of the length of the
// sub string
function maxLength(s, n) {
var ans = -2147483648;
var A = [];
var L = [];
var R = [];
var freq = new Array(n + 5).fill(0);
// for each of the character 'a' to 'z'
for (var i = 0; i < 26; i++) {
var count = 0;
// finding frequency prefix array of the
// character
for (var j = 0; j < n; j++) {
if (s[j].charCodeAt(0) - "a".charCodeAt(0) === i)
count++;
freq[j] = count;
}
// Finding the r[] and l[] arrays.
for (var j = 1; j < n; j++) {
L.push(2 * freq[j - 1] - j);
R.push(2 * freq[j] - j);
}
var max_len = -2147483648;
var min_val = 2147483648;
// for each j from 0 to n
for (var j = 0; j < L.length; j++) {
min_val = Math.min(min_val, L[j]);
A.push(min_val);
var l = 0,
r = j;
// Finding the lower bound of i.
while (l <= r) {
var mid = (l + r) >> 1;
if (A[mid] <= R[j]) {
max_len = Math.max(max_len, j - mid + 1);
r = mid - 1;
}
else {
l = mid + 1;
}
}
}
// storing the maximum value of i - j + 1
ans = Math.max(ans, max_len);
// clearing all the vector so that it can
// be used for other characters.
A = [];
R = [];
L = [];
}
return ans;
}
// Driver Code
var s = "ababbbacbcbcca";
var n = s.length;
document.write(maxLength(s, n));
</script>
Producción:
13
Complejidad del tiempo: O(26*N*logN)
Espacio Auxiliar: O(1)