Substrings que comienzan y terminan con un carácter y tienen al menos otro

Dada la string str que contiene solo los caracteres x e y , la tarea es contar todas las substrings que comienzan y terminan con una x y tienen al menos una sola y .

Ejemplos:  

Entrada: str = “xyyxx” 
Salida: 2 
“xyyx” y “xyyxx” son las únicas substrings válidas.

Entrada: str = “xyy” 
Salida: 0 

Acercarse:  

• Cree una array countX[] donde countX[i] almacene el total x de i a n – 1 .
• Ahora, para cada x en la string, encuentra la primera y que aparece después de esta x .
• Y actualice count = count + countX[indexOf(y)] porque, con esta x como índice inicial, todas las substrings serán válidas y terminarán en cualquier x después de encontrar y .
• Devuelve la cuenta al final.

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

// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
 
// Function that returns the index of next occurrence
// of the character c in string str starting from index start
int nextIndex(string str, int start, char c)
{
 
    // Starting from start
    for (int i = start; i < str.length(); i++) {
 
        // If current character = c
        if (str[i] == c)
            return i;
    }
 
    // Not found
    return -1;
}
 
// Function to return the count of required sub-strings
int countSubStrings(string str)
{
    int i, n = str.length();
 
    // Stores running count of 'x' starting from the end
    int countX[n];
 
    int count = 0;
    for (i = n - 1; i >= 0; i--) {
        if (str[i] == 'x')
            count++;
        countX[i] = count;
    }
 
    // Next index of 'x' starting from index 0
    int nextIndexX = nextIndex(str, 0, 'x');
 
    // Next index of 'y' starting from index 0
    int nextIndexY = nextIndex(str, 0, 'y');
 
    // To store the count of required sub-strings
    count = 0;
    while (nextIndexX != -1 && nextIndexY != -1) {
 
        // If 'y' appears before 'x'
        // it won't contribute to a valid sub-string
        if (nextIndexX > nextIndexY) {
 
            // Find next occurrence of 'y'
            nextIndexY = nextIndex(str, nextIndexY + 1, 'y');
            continue;
        }
 
        // If 'y' appears after 'x'
        // every sub-string ending at an 'x' appearing after this 'y'
        // and starting with the current 'x' is a valid sub-string
        else {
            count += countX[nextIndexY];
 
            // Find next occurrence of 'x'
            nextIndexX = nextIndex(str, nextIndexX + 1, 'x');
        }
    }
 
    // Return the count
    return count;
}
 
// Driver code
int main()
{
 
    string s = "xyyxx";
 
    cout << countSubStrings(s);
}
 
// This code is contributed by ihritik

// Java implementation of the approach
public class GFG {
 
    // Function that returns the index of next occurrence
    // of the character c in string str starting from index start
    static int nextIndex(String str, int start, char c)
    {
 
        // Starting from start
        for (int i = start; i < str.length(); i++) {
 
            // If current character = c
            if (str.charAt(i) == c)
                return i;
        }
 
        // Not found
        return -1;
    }
 
    // Function to return the count of required sub-strings
    static int countSubStrings(String str)
    {
        int i, n = str.length();
 
        // Stores running count of 'x' starting from the end
        int countX[] = new int[n];
 
        int count = 0;
        for (i = n - 1; i >= 0; i--) {
            if (str.charAt(i) == 'x')
                count++;
            countX[i] = count;
        }
 
        // Next index of 'x' starting from index 0
        int nextIndexX = nextIndex(str, 0, 'x');
 
        // Next index of 'y' starting from index 0
        int nextIndexY = nextIndex(str, 0, 'y');
 
        // To store the count of required sub-strings
        count = 0;
        while (nextIndexX != -1 && nextIndexY != -1) {
 
            // If 'y' appears before 'x'
            // it won't contribute to a valid sub-string
            if (nextIndexX > nextIndexY) {
 
                // Find next occurrence of 'y'
                nextIndexY = nextIndex(str, nextIndexY + 1, 'y');
                continue;
            }
 
            // If 'y' appears after 'x'
            // every sub-string ending at an 'x' appearing after this 'y'
            // and starting with the current 'x' is a valid sub-string
            else {
                count += countX[nextIndexY];
 
                // Find next occurrence of 'x'
                nextIndexX = nextIndex(str, nextIndexX + 1, 'x');
            }
        }
 
        // Return the count
        return count;
    }
 
    // Driver code
    public static void main(String[] args)
    {
 
        String s = "xyyxx";
 
        System.out.println(countSubStrings(s));
    }
}

# Python3 implementation of the approach
 
# Function that returns the index of next occurrence
# of the character c in string str starting from index start
def nextIndex(str, start, c):
 
 
    # Starting from start
    for i in range(start,len(str)):
 
        # If current character = c
        if (str[i] == c):
            return i;
     
 
    # Not found
    return -1;
 
 
# Function to return the count of required sub-strings
def countSubStrings(str):
 
    n = len(str)
 
    # Stores running count of 'x' starting from the end
    countX=[0]*n;
 
    count = 0;
    for i in range(n-1,-1,-1):
        if (str[i] == 'x'):
            count=count+1
        countX[i] = count
     
 
    # Next index of 'x' starting from index 0
    nextIndexX = nextIndex(str, 0, 'x')
 
    # Next index of 'y' starting from index 0
    nextIndexY = nextIndex(str, 0, 'y')
 
    # To store the count of required sub-strings
    count = 0;
    while (nextIndexX != -1 and nextIndexY != -1):
 
        # If 'y' appears before 'x'
        # it won't contribute to a valid sub-string
        if (nextIndexX > nextIndexY):
 
            # Find next occurrence of 'y'
            nextIndexY = nextIndex(str, nextIndexY + 1, 'y')
            continue
         
 
        # If 'y' appears after 'x'
        # every sub-string ending at an 'x' appearing after this 'y'
        # and starting with the current 'x' is a valid sub-string
        else :
            count += countX[nextIndexY]
 
            # Find next occurrence of 'x'
            nextIndexX = nextIndex(str, nextIndexX + 1, 'x');
         
     
 
    # Return the count
    return count
 
 
# Driver code
 
 
s = "xyyxx";
 
print(countSubStrings(s));
 
 
# This code is contributed by ihritik

// C# implementation of the approach
 
using System;
 
public class GFG {
 
    // Function that returns the index of next occurrence
    // of the character c in string str starting from index start
    static int nextIndex(string str, int start, char c)
    {
 
        // Starting from start
        for (int i = start; i < str.Length; i++) {
 
            // If current character = c
            if (str[i] == c)
                return i;
        }
 
        // Not found
        return -1;
    }
 
    // Function to return the count of required sub-strings
    static int countSubStrings(string str)
    {
        int i, n = str.Length ;
 
        // Stores running count of 'x' starting from the end
        int []countX = new int[n];
 
        int count = 0;
        for (i = n - 1; i >= 0; i--) {
            if (str[i] == 'x')
                count++;
            countX[i] = count;
        }
 
        // Next index of 'x' starting from index 0
        int nextIndexX = nextIndex(str, 0, 'x');
 
        // Next index of 'y' starting from index 0
        int nextIndexY = nextIndex(str, 0, 'y');
 
        // To store the count of required sub-strings
        count = 0;
        while (nextIndexX != -1 && nextIndexY != -1) {
 
            // If 'y' appears before 'x'
            // it won't contribute to a valid sub-string
            if (nextIndexX > nextIndexY) {
 
                // Find next occurrence of 'y'
                nextIndexY = nextIndex(str, nextIndexY + 1, 'y');
                continue;
            }
 
            // If 'y' appears after 'x'
            // every sub-string ending at an 'x' appearing after this 'y'
            // and starting with the current 'x' is a valid sub-string
            else {
                count += countX[nextIndexY];
 
                // Find next occurrence of 'x'
                nextIndexX = nextIndex(str, nextIndexX + 1, 'x');
            }
        }
 
        // Return the count
        return count;
    }
 
    // Driver code
    public static void Main()
    {
 
        string s = "xyyxx";
 
        Console.WriteLine(countSubStrings(s));
    }
    // This code is contributed by Ryuga
}

<?php
// PHP implementation of the approach
  
// Function that returns the index of next occurrence
// of the character c in string str starting from index start
function nextIndex($str, $start, $c)
{
  
    // Starting from start
    for ($i = $start; $i < strlen($str); $i++) {
  
        // If current character = c
        if ($str[$i] == $c)
            return $i;
    }
  
    // Not found
    return -1;
}
  
// Function to return the count of required sub-strings
function countSubStrings($str)
{
    $n = strlen($str);
  
    // Stores running count of 'x' starting from the end
    $countX = array(0,$n,NULL);
  
    $count = 0;
    for ($i = $n - 1; $i >= 0; $i--) {
        if ($str[$i] == 'x')
            $count++;
        $countX[$i] = $count;
    }
  
    // Next index of 'x' starting from index 0
    $nextIndexX = nextIndex($str, 0, 'x');
  
    // Next index of 'y' starting from index 0
    $nextIndexY = nextIndex($str, 0, 'y');
  
    // To store the count of required sub-strings
    $count = 0;
    while ($nextIndexX != -1 && $nextIndexY != -1) {
  
        // If 'y' appears before 'x'
        // it won't contribute to a valid sub-string
        if ($nextIndexX > $nextIndexY) {
  
            // Find next occurrence of 'y'
            $nextIndexY = nextIndex($str, $nextIndexY + 1, 'y');
            continue;
        }
  
        // If 'y' appears after 'x'
        // every sub-string ending at an 'x' appearing after this 'y'
        // and starting with the current 'x' is a valid sub-string
        else {
            $count += $countX[$nextIndexY];
  
            // Find next occurrence of 'x'
            $nextIndexX = nextIndex($str, $nextIndexX + 1, 'x');
        }
    }
  
    // Return the count
    return $count;
}
  
// Driver code
 
$s = "xyyxx";
echo countSubStrings($s);
?>

<script>
// Javascript implementation of the approach
     
    // Function that returns the index of next occurrence
    // of the character c in string str starting from index start
    function nextIndex(str,start,c)
    {
        // Starting from start
        for (let i = start; i < str.length; i++) {
   
            // If current character = c
            if (str[i] == c)
                return i;
        }
   
        // Not found
        return -1;
    }
     
    // Function to return the count of required sub-strings
    function countSubStrings(str)
    {
        let i, n = str.length;
   
        // Stores running count of 'x' starting from the end
        let countX = new Array(n);
   
        let count = 0;
        for (i = n - 1; i >= 0; i--) {
            if (str[i] == 'x')
                count++;
            countX[i] = count;
        }
   
        // Next index of 'x' starting from index 0
        let nextIndexX = nextIndex(str, 0, 'x');
   
        // Next index of 'y' starting from index 0
        let nextIndexY = nextIndex(str, 0, 'y');
   
        // To store the count of required sub-strings
        count = 0;
        while (nextIndexX != -1 && nextIndexY != -1) {
   
            // If 'y' appears before 'x'
            // it won't contribute to a valid sub-string
            if (nextIndexX > nextIndexY) {
   
                // Find next occurrence of 'y'
                nextIndexY = nextIndex(str, nextIndexY + 1, 'y');
                continue;
            }
   
            // If 'y' appears after 'x'
            // every sub-string ending at an 'x' appearing after this 'y'
            // and starting with the current 'x' is a valid sub-string
            else {
                count += countX[nextIndexY];
   
                // Find next occurrence of 'x'
                nextIndexX = nextIndex(str, nextIndexX + 1, 'x');
            }
        }
   
        // Return the count
        return count;
    }
     
    // Driver code
    let s = "xyyxx";
    document.write(countSubStrings(s));
 
 
// This code is contributed by avanitrachhadiya2155
</script>

2

Complejidad temporal: O(n ² )

Espacio Auxiliar: O(n), donde n es la longitud de la string s.