Longitud de la substring más larga que consta solo de vocales en orden no creciente

Dada una string S de tamaño N que consiste en letras minúsculas, la tarea es imprimir la longitud de la substring más larga que consiste solo en vocales ordenadas en orden no creciente.

Ejemplos:

Entrada: S = “ueiaoaeiouuoiea”
Salida: 6
Explicación:  La única substring que consta solo de vocales en orden no creciente es la substring {S[9], S[15]}, que es “uuoiea”.

Entrada: S = “uuuioea”
Salida: 0

 

Enfoque: el problema dado se puede resolver usando HashSet . Siga los pasos a continuación para resolver el problema:

  • Almacene todas las vocales en una array, digamos ch[] , en orden decreciente.
  • Inicialice tres variables res, j y cuente como 0 para almacenar la longitud más larga de la substring requerida, para iterar sobre todas las vocales y para almacenar la longitud de la substring actual que satisfaga las condiciones respectivamente.
  • Además, inicialice un HashSet , digamos mp , para almacenar todos los caracteres distintos de la substring actual que satisfagan las condiciones.
  • Itere sobre los caracteres de la string S usando una variable i y realice las siguientes operaciones:
    • Si S[i] es igual a ch[j] , agregue S[i] a mp y luego incremente j y cuente de 1 en 1 . Si el tamaño de mp es igual a 5 , actualice res a un máximo de res y cuente .
    • De lo contrario, si j + 1 es menor que 5 y S[i] es igual a ch[j + 1] , entonces incremente j y cuente de 1 en 1 y agregue S[i] a mp . Si el tamaño de mp es igual a 5 , actualice res a un máximo de res y cuente .
    • De lo contrario, si S[i] es igual a ‘ u ‘, entonces asigne 0 a j y 1 para contar y sume S[i] a mp . De lo contrario, asigne 0 tanto a j como a count .
  • Después de completar los pasos anteriores, imprima el valor de res como resultado.

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 length of the
// longest substring consisting only
// of vowels in non-increasing order
int count(string S, int N)
{
 
    // Stores all vowels in decreasing order
    char ch[] = { 'u', 'o', 'i', 'e', 'a' };
 
    // Stores current index of array ch[]
    int j = 0;
 
    // Stores the result
    int res = 0;
 
    // Stores the count
    // of current substring
    int count = 0;
 
    // Declare a HashSet to store the vowels
    unordered_set<char> mp;
 
    // Traverse the string, S
    for(int i = 0; i < N; ++i)
    {
         
        // If S[i] is equal to ch[j]
        if (S[i] == ch[j])
        {
             
            // Increment count by 1
            ++count;
 
            // Add S[i] in the mp
            mp.insert(S[i]);
 
            // If length of mp is 5, update res
            if (mp.size() == 5)
            {
                res = max(res, count);
            }
        }
 
        // Else if j+1 is less than 5 and
        // S[i] is equal to ch[j+1]
        else if (j + 1 < 5 && S[i] == ch[j + 1])
        {
             
            // Add the S[i] in the mp
            mp.insert(S[i]);
 
            // Increment count by 1
            ++count;
 
            // Increment j by 1
            j++;
 
            // If length of mp is 5, update res
            if (mp.size() == 5)
            {
                res = max(res, count);
            }
        }
        else
        {
             
            // Clear the mp
            mp.clear();
 
            // If S[i] is 'u'
            if (S[i] == 'u')
            {
                 
                // Add S[i] in the mp
                mp.insert('u');
 
                // Update j and assign 1 to count
                j = 0;
                count = 1;
            }
 
            // Else assign 0 to j and count
            else
            {
                j = 0;
                count = 0;
            }
        }
    }
 
    // Return the result
    return res;
}
 
// Driver Code
int main()
{
    string S = "ueiaoaeiouuoiea";
    int N = S.size();
 
    // Function Call
    cout << count(S, N);
 
    return 0;
}
 
// This code is contributed by Kingash

Java

// Java program for the above approach
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Function to find length of the
    // longest substring consisting only
    // of vowels in non-increasing order
    static int count(String S, int N)
    {
 
        // Stores all vowels in decreasing order
        char ch[] = { 'u', 'o', 'i', 'e', 'a' };
 
        // Stores current index of array ch[]
        int j = 0;
 
        // Stores the result
        int res = 0;
 
        // Stores the count
        // of current substring
        int count = 0;
 
        // Declare a HashSet to store the vowels
        HashSet<Character> mp = new HashSet<>();
 
        // Traverse the string, S
        for (int i = 0; i < N; ++i) {
 
            // If S[i] is equal to ch[j]
            if (S.charAt(i) == ch[j]) {
 
                // Increment count by 1
                ++count;
 
                // Add S[i] in the mp
                mp.add(S.charAt(i));
 
                // If length of mp is 5, update res
                if (mp.size() == 5) {
                    res = Math.max(res, count);
                }
            }
 
            // Else if j+1 is less than 5 and
            // S[i] is equal to ch[j+1]
            else if (j + 1 < 5
                     && S.charAt(i) == ch[j + 1]) {
 
                // Add the S[i] in the mp
                mp.add(S.charAt(i));
 
                // Increment count by 1
                ++count;
 
                // Increment j by 1
                j++;
 
                // If length of mp is 5, update res
                if (mp.size() == 5) {
                    res = Math.max(res, count);
                }
            }
            else {
 
                // Clear the mp
                mp.clear();
 
                // If S[i] is 'u'
                if (S.charAt(i) == 'u') {
 
                    // Add S[i] in the mp
                    mp.add('u');
 
                    // Update j and assign 1 to count
                    j = 0;
                    count = 1;
                }
 
                // Else assign 0 to j and count
                else {
                    j = 0;
                    count = 0;
                }
            }
        }
 
        // Return the result
        return res;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        // Given Input
        String S = "ueiaoaeiouuoiea";
        int N = S.length();
 
        // Function Call
        System.out.println(count(S, N));
    }
}

Python3

# Python3 program for the above approach
 
# Function to find length of the
# longest substring consisting only
# of vowels in non-increasing order
def count1(S, N):
 
    # Stores all vowels in decreasing order
    ch = ['u', 'o', 'i', 'e', 'a']
 
    # Stores current index of array ch[]
    j = 0
 
    # Stores the result
    res = 0
 
    # Stores the count
    # of current substring
    count = 0;
 
    # Declare a HashSet to store the vowels
    mp = set()
 
    # Traverse the string, S
    for i in range(N):
         
        # If S[i] is equal to ch[j]
        if (S[i] == ch[j]):
             
            # Increment count by 1
            count += 1
 
            # Add S[i] in the mp
            mp.add(S[i])
 
            # If length of mp is 5, update res
            if (len(mp) == 5):
                res = max(res, count)
 
        # Else if j+1 is less than 5 and
        # S[i] is equal to ch[j+1]
        elif (j + 1 < 5 and S[i] == ch[j + 1]):
             
            # Add the S[i] in the mp
            mp.add(S[i])
 
            # Increment count by 1
            count += 1
 
            # Increment j by 1
            j += 1
 
            # If length of mp is 5, update res
            if (len(mp) == 5):
                res = max(res, count)
        else:
             
            # Clear the mp
            mp.clear()
 
            # If S[i] is 'u'
            if (S[i] == 'u'):
                 
                # Add S[i] in the mp
                mp.add('u')
 
                # Update j and assign 1 to count
                j = 0
                count = 1
 
            # Else assign 0 to j and count
            else:
                j = 0
                count = 0
 
    # Return the result
    return res
 
# Driver Code
if __name__ == '__main__':
     
    S = "ueiaoaeiouuoiea"
    N = len(S)
 
    # Function Call
    print(count1(S, N))
     
# This code is contributed by SURENDRA_GANGWAR

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
 
  // Function to find length of the
  // longest substring consisting only
  // of vowels in non-increasing order
  static int count(string S, int N)
  {
 
    // Stores all vowels in decreasing order
    char[] ch = { 'u', 'o', 'i', 'e', 'a' };
 
    // Stores current index of array ch[]
    int j = 0;
 
    // Stores the result
    int res = 0;
 
    // Stores the count
    // of current substring
    int count = 0;
 
    // Declare a HashSet to store the vowels
    HashSet<char> mp = new HashSet<char>();
 
    // Traverse the string, S
    for (int i = 0; i < N; ++i) {
 
      // If S[i] is equal to ch[j]
      if (S[i] == ch[j]) {
 
        // Increment count by 1
        ++count;
 
        // Add S[i] in the mp
        mp.Add(S[i]);
 
        // If length of mp is 5, update res
        if (mp.Count == 5) {
          res = Math.Max(res, count);
        }
      }
 
      // Else if j+1 is less than 5 and
      // S[i] is equal to ch[j+1]
      else if (j + 1 < 5 && S[i] == ch[j + 1]) {
 
        // Add the S[i] in the mp
        mp.Add(S[i]);
 
        // Increment count by 1
        ++count;
 
        // Increment j by 1
        j++;
 
        // If length of mp is 5, update res
        if (mp.Count == 5) {
          res = Math.Max(res, count);
        }
      }
      else {
 
        // Clear the mp
        mp.Clear();
 
        // If S[i] is 'u'
        if (S[i] == 'u') {
 
          // Add S[i] in the mp
          mp.Add('u');
 
          // Update j and assign 1 to count
          j = 0;
          count = 1;
        }
 
        // Else assign 0 to j and count
        else {
          j = 0;
          count = 0;
        }
      }
    }
 
    // Return the result
    return res;
  }
 
  // Driver Code
  public static void Main(string[] args)
  {
 
    // Given Input
    string S = "ueiaoaeiouuoiea";
    int N = S.Length;
 
    // Function Call
    Console.WriteLine(count(S, N));
  }
}
 
// This code is contributed by ukasp.

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to find length of the
// longest substring consisting only
// of vowels in non-increasing order
function count(S, N)
{
     
    // Stores all vowels in decreasing order
    let ch = [ 'u', 'o', 'i', 'e', 'a' ];
 
    // Stores current index of array ch[]
    let j = 0;
 
    // Stores the result
    let res = 0;
 
    // Stores the count
    // of current substring
    let count = 0;
 
    // Declare a HashSet to store the vowels
    let mp = new Map();
 
    // Traverse the string, S
    for(let i = 0; i < N; ++i)
    {
 
        // If S[i] is equal to ch[j]
        if (S[i] == ch[j])
        {
 
            // Increment count by 1
            ++count;
 
            // Add S[i] in the mp
            mp.set(S[i], "");
 
            // If length of mp is 5, update res
            if (mp.size == 5)
            {
                res = Math.max(res, count);
            }
        }
 
        // Else if j+1 is less than 5 and
        // S[i] is equal to ch[j+1]
        else if (j + 1 < 5 && S[i] == ch[j + 1])
        {
             
            // Add the S[i] in the mp
            mp.set(S[i], "");
 
            // Increment count by 1
            ++count;
 
            // Increment j by 1
            j++;
 
            // If length of mp is 5, update res
            if (mp.size == 5)
            {
                res = Math.max(res, count);
            }
        }
        else
        {
 
            // Clear the mp
            mp.clear();
 
            // If S[i] is 'u'
            if (S[i] == 'u')
            {
 
                // Add S[i] in the mp
                mp.set('u', "");
 
                // Update j and assign 1 to count
                j = 0;
                count = 1;
            }
 
            // Else assign 0 to j and count
            else
            {
                j = 0;
                count = 0;
            }
        }
    }
 
    // Return the result
    return res;
}
 
// Driver Code
let S = "ueiaoaeiouuoiea";
let N = S.length;
 
// Function Call
document.write(count(S, N));
 
// This code is contributed by _saurabh_jaiswal
 
</script>
Producción: 

6

 

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

Publicación traducida automáticamente

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