La substring más larga sin un par de caracteres adyacentes son alfabetos ingleses adyacentes

Posted on by Rudeus Greyrat

Dada una string S que consta de alfabetos ingleses en minúsculas, la tarea es encontrar la substring más larga de la string dada de modo que no haya dos caracteres adyacentes que sean alfabetos ingleses vecinos.

Ejemplos:

Entrada: S = “aabdml”
Salida: “bdm”
Explicación: La substring “bdm” es la substring más larga que satisface la condición dada.

Entrada: S = “abc”
Salida: “a”
Explicación: Las substrings “a”, “b”, “c” satisfacen la condición dada. Imprime cualquiera de ellos.

Enfoque: siga los pasos a continuación para resolver el problema:

  1. Inicialice una string vacía, digamos T , para almacenar todas las substrings temporales durante la iteración.
  2. Inicialice otra string, digamos ans , para almacenar la substring más larga según las condiciones dadas y una variable, digamos len , para almacenar la longitud de la substring más larga.
  3. Agregue el primer carácter de la string a ans .
  4. Recorra la string en el rango de índices [1, S.length()] y realice las siguientes operaciones:
    • Si la diferencia absoluta entre los valores ASCII de los caracteres adyacentes es 1 , actualice ans y la longitud de la string más larga y establezca T igual al carácter actual para la siguiente iteración.
    • De lo contrario, agregue el carácter actual a la string T .
  5. Verifique nuevamente la substring más larga y actualice los valores en consecuencia.
  6. Imprime la substring más larga obtenida en la variable ans .

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 the longest substring
// satisfying the given condition
void findSubstring(string S)
{
    // Stores all temporary substrings
    string T = "";
 
    // Stores the longest substring
    string ans = "";
 
    // Stores the length
    // of the substring T
    int l = 0;
 
    // Stores the first
    // character of string S
    T += S[0];
 
    // Traverse the string
    for (int i = 1; i < S.length(); i++) {
 
        // If the absolute difference is 1
        if (abs(S[i] - S[i - 1]) == 1) {
 
            // Update the length of
            // substring T
            l = T.length();
 
            // Update the longest substring
            if (l > ans.length()) {
                ans = T;
            }
 
            T = "";
            T += S[i];
        }
 
        // Otherwise, stores the current
        // character
        else {
            T += S[i];
        }
    }
 
    // Again checking for
    // longest substring
    // and update accordingly
    l = (int)T.length();
 
    if (l > (int)ans.length()) {
        ans = T;
    }
 
    // Print the longest substring
    cout << ans << endl;
}
 
// Driver Code
int main()
{
    // Given string
    string S = "aabdml";
 
    // Function call to find
    // the longest substring
    // satisfying given condition
    findSubstring(S);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
class GFG
{
 
  // Function to find the longest substring
  // satisfying the given condition
  static void findSubstring(String S)
  {
 
    // Stores all temporary substrings
    String T = "";
 
    // Stores the longest substring
    String ans = "";
 
    // Stores the length
    // of the substring T
    int l = 0;
 
    // Stores the first
    // character of string S
    T += S.charAt(0);
 
    // Traverse the string
    for (int i = 1; i < S.length(); i++) {
 
      // If the absolute difference is 1
      if (Math.abs(S.charAt(i) - S.charAt(i - 1))
          == 1) {
 
        // Update the length of
        // substring T
        l = T.length();
 
        // Update the longest substring
        if (l > ans.length()) {
          ans = T;
        }
 
        T = "";
        T += S.charAt(i);
      }
 
      // Otherwise, stores the current
      // character
      else {
        T += S.charAt(i);
      }
    }
 
    // Again checking for
    // longest substring
    // and update accordingly
    l = T.length();
    if (l > ans.length()) {
      ans = T;
    }
 
    // Print the longest substring
    System.out.println(ans);
  }
 
  // Driver Code
  public static void main(String[] args)
  {
 
    // Given string
    String S = "aabdml";
 
    // Function call to find
    // the longest substring
    // satisfying given condition
    findSubstring(S);
  }
}
 
// This code is contributed by Dharanendra L V.

Python3

# Python3 program for
# the above approach
 
# Function to find the longest substring
# satisfying the given condition
def findSubstring(S):
   
    # Stores all temporary substrings
    T = ""
 
    # Stores the longest substring
    ans = ""
 
    # Stores the length
    # of the subT
    l = 0
 
    # Stores the first
    # character of S
    T += S[0]
 
    # Traverse the string
    for i in range(1,len(S)):
 
        # If the absolute difference is 1
        if (abs(ord(S[i]) - ord(S[i - 1])) == 1):
 
            # Update the length of
            # subT
            l = len(T)
 
            # Update the longest substring
            if (l > len(ans)):
                ans = T
            T = ""
            T += S[i]
 
        # Otherwise, stores the current
        # character
        else:
            T += S[i]
 
    # Again checking for
    # longest substring
    # and update accordingly
    l = len(T)
    if (l > len(ans)):
        ans = T
 
    # Print the longest substring
    print (ans)
 
# Driver Code
if __name__ == '__main__':
   
    # Given string
    S = "aabdml"
 
    # Function call to find
    # the longest substring
    # satisfying given condition
    findSubstring(S)
 
    # This code is contributed by mohit kumar 29.

C#

// C# program for the above approach
using System;
public class GFG
{
   
// Function to find the longest substring
// satisfying the given condition
static void findSubstring(string S)
{
   
    // Stores all temporary substrings
    string T = "";
 
    // Stores the longest substring
    string ans = "";
 
    // Stores the length
    // of the substring T
    int l = 0;
 
    // Stores the first
    // character of string S
    T += S[0];
 
    // Traverse the string
    for (int i = 1; i < S.Length; i++)
    {
 
        // If the absolute difference is 1
        if (Math.Abs(S[i] - S[i - 1]) == 1)
        {
 
            // Update the length of
            // substring T
            l = T.Length;
 
            // Update the longest substring
            if (l > ans.Length)
            {
                ans = T;
            }
 
            T = "";
            T += S[i];
        }
 
        // Otherwise, stores the current
        // character
        else
        {
            T += S[i];
        }
    }
 
    // Again checking for
    // longest substring
    // and update accordingly
    l = T.Length;
    if (l > ans.Length)
    {
        ans = T;
    }
 
    // Print the longest substring
    Console.Write(ans);
}
 
 
// Driver Code
public static void Main(String[] args)
{
   
    // Given string
    string S = "aabdml";
 
    // Function call to find
    // the longest substring
    // satisfying given condition
    findSubstring(S);
}
}
 
// This code is contributed by code_hunt.

Javascript

<script>
 
      // JavaScript program for the above approach
       
      // Function to find the longest substring
      // satisfying the given condition
      function findSubstring(S) {
        // Stores all temporary substrings
        var T = "";
 
        // Stores the longest substring
        var ans = "";
 
        // Stores the length
        // of the substring T
        var l = 0;
 
        // Stores the first
        // character of string S
        T += S[0];
 
        // Traverse the string
        for (var i = 1; i < S.length; i++) {
          // If the absolute difference is 1
          if (Math.abs(S[i].charCodeAt(0) -
          S[i - 1].charCodeAt(0)) === 1)
          {
            // Update the length of
            // substring T
            l = T.length;
 
            // Update the longest substring
            if (l > ans.length) {
              ans = T;
            }
 
            T = "";
            T += S[i];
          }
 
          // Otherwise, stores the current
          // character
          else {
            T += S[i];
          }
        }
 
        // Again checking for
        // longest substring
        // and update accordingly
        l = T.length;
        if (l > ans.length) {
          ans = T;
        }
 
        // Print the longest substring
        document.write(ans);
      }
 
      // Driver Code
      // Given string
      var S = "aabdml";
 
      // Function call to find
      // the longest substring
      // satisfying given condition
      findSubstring(S);
       
</script>
Producción: 

bdm

 

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

Publicación traducida automáticamente

Artículo escrito por ankushingle8523 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 *