Recuento de pares de índices (i, j) tales que la string después de eliminar el i-ésimo carácter es igual a la string después de eliminar el j-ésimo carácter

Dada una string str de N caracteres, la tarea es calcular el recuento de pares desordenados válidos de (i, j) de modo que la string después de eliminar el i ^-ésimo carácter sea igual a la string después de eliminar el j ^-ésimo carácter.

Ejemplos:

Entrada: str = “aabb”
Salida: 2
Explicación: La string después de la eliminación del primer elemento es “abb” y la string después de la eliminación del segundo elemento es “abb”. De manera similar, la string después de la eliminación del tercer elemento es «aab» y la string después de la eliminación del cuarto elemento es «aab». Por lo tanto, el número de pares válidos de (i, j) es 2, es decir, (1, 2) y (3, 4).

Entrada: str = “aaaaaa”
Salida: 15

Enfoque: El problema dado se puede resolver usando las siguientes observaciones:

• Si S _i = S _j , entonces S _i = S _i+1 = S _i+2 … = S _j debe ser cierto.
• Además, si S _i = S _j , entonces str[i] = str[i+1] = str[i+2] … = str[j] también debe ser cierto.

Por lo tanto, usando las observaciones anteriores, la técnica de dos punteros se puede usar para calcular los intervalos (l, r) en la string str tal que str[l] = str[l+1] … = str[r] , y para cada válido (l, r) , el recuento de pares válidos será ^{r – l} C ₂ .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the count of valid
// pairs (i, j) such that string after
// deleting ith character is equal to
// string after deleting jth character
int countValidPairs(string str, int N)
{
 
    // Stores the required count
    int ans = 0;
 
    // Loop to iterate the given array
    for (int l = 0, r; l < N; l = r) {
 
        // initial end point
        r = l;
 
        // Loop to calculate the range
        // [l, r] such that all characters
        // from l to r are equal
        while (r < N && str[l] == str[r]) {
            r++;
        }
 
        // Update the answer
        ans += ((r - l) * (r - l - 1)) / 2;
    }
 
    // Return Answer
    return ans;
}
 
// Driver Code
int main()
{
    string str = "aaaaaa";
    cout << countValidPairs(str, str.length());
 
    return 0;
}

// Java program for the above approach
import java.util.*;
public class GFG
{
   
// Function to find the count of valid
// pairs (i, j) such that string after
// deleting ith character is equal to
// string after deleting jth character
static int countValidPairs(String str, int N)
{
 
    // Stores the required count
    int ans = 0;
 
    // Loop to iterate the given array
    for (int l = 0, r; l < N; l = r) {
 
        // initial end point
        r = l;
 
        // Loop to calculate the range
        // [l, r] such that all characters
        // from l to r are equal
        Character c1 = str.charAt(l);
        Character c2 = str.charAt(r);
        while (r < N && c1.equals(c2)) {
            r++;
        }
 
        // Update the answer
        ans += ((r - l) * (r - l - 1)) / 2;
    }
 
    // Return Answer
    return ans;
}
 
// Driver Code
public static void main(String args[])
{
    String str = "aaaaaa";
    System.out.print(countValidPairs(str, str.length()));
}
}
 
// This code is contributed by Samim Hossain Mondal.

# Python program for the above approach
 
# Function to find the count of valid
# pairs (i, j) such that string after
# deleting ith character is equal to
# string after deleting jth character
def countValidPairs(str, N):
 
    # Stores the required count
    ans = 0;
 
    # Loop to iterate the given array
    l = 0;
    r = None;
     
    while(l < N):
        # initial end point
        r = l;
 
        # Loop to calculate the range
        # [l, r] such that all characters
        # from l to r are equal
        while (r < N and str[l] == str[r]):
            r += 1
 
        # Update the answer
        ans += ((r - l) * (r - l - 1)) // 2;
 
        l = r;
     
    # Return Answer
    return ans;
 
# Driver Code
str = "aaaaaa";
print(countValidPairs(str, len(str)));
 
# This code is contributed by Saurabh Jaiswal

// C# program for the above approach
using System;
class GFG
{
   
// Function to find the count of valid
// pairs (i, j) such that string after
// deleting ith character is equal to
// string after deleting jth character
static int countValidPairs(string str, int N)
{
 
    // Stores the required count
    int ans = 0;
 
    // Loop to iterate the given array
    for (int l = 0, r; l < N; l = r) {
 
        // initial end point
        r = l;
 
        // Loop to calculate the range
        // [l, r] such that all characters
        // from l to r are equal
        char c1 = str[l];
        char c2 = str[r];
        while (r < N && c1.Equals(c2)) {
            r++;
        }
 
        // Update the answer
        ans += ((r - l) * (r - l - 1)) / 2;
    }
 
    // Return Answer
    return ans;
}
 
// Driver Code
public static void Main()
{
    string str = "aaaaaa";
    Console.Write(countValidPairs(str, str.Length));
 
}
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
// Javascript program for the above approach
 
// Function to find the count of valid
// pairs (i, j) such that string after
// deleting ith character is equal to
// string after deleting jth character
function countValidPairs(str, N)
{
 
    // Stores the required count
    let ans = 0;
 
    // Loop to iterate the given array
    for (let l = 0, r; l < N; l = r) {
 
        // initial end point
        r = l;
 
        // Loop to calculate the range
        // [l, r] such that all characters
        // from l to r are equal
        while (r < N && str[l] == str[r]) {
            r++;
        }
 
        // Update the answer
        ans += ((r - l) * (r - l - 1)) / 2;
    }
 
    // Return Answer
    return ans;
}
 
// Driver Code
let str = "aaaaaa";
document.write(countValidPairs(str, str.length));
 
// This code is contributed by Samim Hossain Mondal.
</script>

15

Complejidad temporal: O(N)
Espacio auxiliar: O(1)