La substring más larga que comienza con X y termina con Y

Posted on by Rudeus Greyrat

Dada una string str , dos caracteres X e Y . La tarea es encontrar la longitud de la substring más larga que comienza con X y termina con Y. Se da que siempre existe una substring que comienza con X y  termina con Y.
Ejemplos: 
 

Entrada: str = “QWERTYASDFZXCV”, X = ‘A’, Y = ‘Z’ 
Salida: 5 
Explicación: 
La substring más grande que comienza con ‘A’ y termina con ‘Z’ = “ASDFZ”. 
Tamaño de la substring = 5.
Entrada: str = «ZABCZ», X = ‘Z’, Y = ‘Z’ 
Salida: 3 
Explicación: 
La substring más grande que comienza con ‘Z’ y termina con ‘Z’ = «ZABCZ» . 
Tamaño de la substring = 5. 
 

Enfoque ingenuo: el enfoque ingenuo consiste en encontrar todas las substrings de la string dada, de entre estas, encontrar la substring más grande que comienza con X y termina con Y . 
 

C++

// C++ program for the naive approach
#include <bits/stdc++.h>
using namespace std;
 
// Function returns length of longest substring starting
// with X and ending with Y
int longestSubstring(string str, char X, char Y)
{
    int n = str.size();
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            // is str[i] == X and str[j] == Y then the
            // substring str[i...j] maybe longest substring
            // that we required
            if (str[i] == X && str[j] == Y) {
                ans = max(ans, j - i + 1);
            }
        }
    }
    return ans;
}
 
// Driver Code
int main()
{
    // Given string str
    string str = "HASFJGHOGAKZZFEGA";
 
    // Starting and Ending characters
    char X = 'A', Y = 'Z';
 
    // Function Call
    cout << longestSubstring(str, X, Y) << "\n";
    return 0;
}
 
// This code is contributed by ajaymakvana

Java

// JAVA program for the naive approach
import java.util.*;
class GFG {
    // Function returns length of longest substring starting
    // with X and ending with Y
    public static int longestSubstring(String str, char X,
                                       char Y)
    {
        int n = str.length();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // is str[i] == X and str[j] == Y then the
                // substring str[i...j] maybe longest
                // substring that we required
                if (str.charAt(i) == X
                    && str.charAt(j) == Y) {
                    ans = Math.max(ans, j - i + 1);
                }
            }
        }
        return ans;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Given string str
        String str = "HASFJGHOGAKZZFEGA";
 
        // Starting and Ending characters
        char X = 'A', Y = 'Z';
 
        // Function Call
        System.out.println(longestSubstring(str, X, Y));
    }
}
// This code is contributed by Taranpreet
Producción

12

Complejidad de Tiempo: O(N 2 ) 
Espacio Auxiliar: O(1)

Enfoque eficiente: para optimizar el enfoque anterior, el recuento de caracteres entre X e Y debe ser el mayor. Entonces, itere sobre la string usando los punteros start y end para encontrar la primera aparición de X desde el índice inicial y la última aparición de Y desde el final. A continuación se muestran los pasos: 
 

  1. Inicializa start = 0 y end = longitud de la string – 1 .
  2. Recorre la string desde el principio y encuentra la primera aparición del carácter X . Que sea en el índice xPos .
  3. Recorre la string desde el principio y encuentra la última aparición del carácter Y . Que sea en el índice yPos .
  4. La longitud de la substring más larga viene dada por (yPos – xPos + 1) .

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 returns length of longest
// substring starting with X and
// ending with Y
int longestSubstring(string str,
                    char X, char Y)
{
    // Length of string
    int N = str.length();
    int start = 0;
    int end = N - 1;
    int xPos = 0;
    int yPos = 0;
 
    // Find the length of the string
    // starting with X from the beginning
    while (true) {
 
        if (str[start] == X) {
            xPos = start;
            break;
        }
        start++;
    }
 
    // Find the length of the string
    // ending with Y from the end
    while (true) {
 
        if (str[end] == Y) {
            yPos = end;
            break;
        }
        end--;
    }
 
    // Longest substring
    int length = (yPos - xPos) + 1;
 
    // Print the length
    cout << length;
}
 
// Driver Code
int main()
{
    // Given string str
    string str = "HASFJGHOGAKZZFEGA";
 
    // Starting and Ending characters
    char X = 'A', Y = 'Z';
 
    // Function Call
    longestSubstring(str, X, Y);
    return 0;
}

Java

// Java program for the above approach
class GFG{
     
// Function returns length of longest
// substring starting with X and
// ending with Y
public static void longestSubstring(String str,
                                    char X, char Y)
{
     
    // Length of string
    int N = str.length();
    int start = 0;
    int end = N - 1;
    int xPos = 0;
    int yPos = 0;
     
    // Find the length of the string
    // starting with X from the beginning
    while (true)
    {
        if (str.charAt(start) == X)
        {
            xPos = start;
            break;
        }
        start++;
    }
     
    // Find the length of the string
    // ending with Y from the end
    while (true)
    {
        if (str.charAt(end) == Y)
        {
            yPos = end;
            break;
        }
        end--;
    }
     
    // Longest substring
    int length = (yPos - xPos) + 1;
     
    // Print the length
    System.out.print(length);
}
 
// Driver code
public static void main(String[] args)
{
     
    // Given string str
    String str = "HASFJGHOGAKZZFEGA";
     
    // Starting and Ending characters
    char X = 'A', Y = 'Z';
     
    // Function Call
    longestSubstring(str, X, Y);
}
}
 
// This code is contributed by divyeshrabadiya07

Python3

# Python3 program for the above approach
 
# Function returns length of longest
# substring starting with X and
# ending with Y
def longestSubstring(str, X, Y):
     
    # Length of string
    N = len(str)
     
    start = 0
    end = N - 1
    xPos = 0
    yPos = 0
 
    # Find the length of the string
    # starting with X from the beginning
    while (True):
        if (str[start] == X):
            xPos = start
            break
             
        start += 1
 
    # Find the length of the string
    # ending with Y from the end
    while (True):
        if (str[end] == Y):
            yPos = end
            break
         
        end -= 1
 
    # Longest substring
    length = (yPos - xPos) + 1
 
    # Print the length
    print(length)
 
# Driver Code
if __name__ == "__main__":
     
    # Given string str
    str = "HASFJGHOGAKZZFEGA"
 
    # Starting and Ending characters
    X = 'A'
    Y = 'Z'
 
    # Function Call
    longestSubstring(str, X, Y)
 
# This code is contributed by sanjoy_62

C#

// C# program for the above approach 
using System;
 
class GFG{
     
// Function returns length of longest
// substring starting with X and
// ending with Y
static void longestSubstring(string str,
                             char X, char Y)
{
     
    // Length of string
    int N = str.Length;
    int start = 0;
    int end = N - 1;
    int xPos = 0;
    int yPos = 0;
     
    // Find the length of the string
    // starting with X from the beginning
    while (true)
    {
        if (str[start] == X)
        {
            xPos = start;
            break;
        }
        start++;
    }
     
    // Find the length of the string
    // ending with Y from the end
    while (true)
    {
        if (str[end] == Y)
        {
            yPos = end;
            break;
        }
        end--;
    }
     
    // Longest substring
    int length = (yPos - xPos) + 1;
     
    // Print the length
    Console.Write(length);
}
 
// Driver code
public static void Main()
{
     
    // Given string str
    string str = "HASFJGHOGAKZZFEGA";
     
    // Starting and Ending characters
    char X = 'A', Y = 'Z';
     
    // Function call
    longestSubstring(str, X, Y);
}
}
 
// This code is contributed by sanjoy_62

Javascript

<script>
      // JavaScript program for the above approach
      // Function returns length of longest
      // substring starting with X and
      // ending with Y
      function longestSubstring(str, X, Y) {
        // Length of string
        var N = str.length;
        var start = 0;
        var end = N - 1;
        var xPos = 0;
        var yPos = 0;
 
        // Find the length of the string
        // starting with X from the beginning
        while (true) {
          if (str[start] === X) {
            xPos = start;
            break;
          }
          start++;
        }
 
        // Find the length of the string
        // ending with Y from the end
        while (true) {
          if (str[end] === Y) {
            yPos = end;
            break;
          }
          end--;
        }
 
        // Longest substring
        var length = yPos - xPos + 1;
 
        // Print the length
        document.write(length);
      }
 
      // Driver code
      // Given string str
      var str = "HASFJGHOGAKZZFEGA";
 
      // Starting and Ending characters
      var X = "A",
        Y = "Z";
      // Function call
      longestSubstring(str, X, Y);
    </script>
Producción

12

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

Publicación traducida automáticamente

Artículo escrito por kivi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *