Comprobar si los caracteres de una string dada están en orden alfabético

Dada una string ‘s’, la tarea es encontrar si los caracteres de la string están en orden alfabético. La string contiene solo caracteres en minúsculas. 
 

Ejemplos: 

Input: Str = "aabbbcc"
Output: In alphabetical order

Input: Str = "aabbbcca"
Output: Not in alphabetical order

Un enfoque simple: 

• Almacene la string en una array de caracteres y ordene la array.
• Si los caracteres en la array ordenada están en el mismo orden que la string, imprima ‘En orden alfabético’.
• Imprima ‘No en orden alfabético’ de lo contrario.

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

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that checks whether
// the string is in alphabetical
// order or not
bool isAlphabaticOrder(string s)
{
    // length of the string
    int n = s.length();
 
    // create a character array
    // of the length of the string
    char c[n];
 
    // assign the string
    // to character array
    for (int i = 0; i < n; i++) {
        c[i] = s[i];
    }
 
    // sort the character array
    sort(c, c + n);
 
    // check if the character array
    // is equal to the string or not
    for (int i = 0; i < n; i++)
        if (c[i] != s[i])
            return false;
         
    return true;   
}
 
// Driver code
int main()
{
    string s = "aabbbcc";
 
    // check whether the string is
    // in alphabetical order or not
    if (isAlphabaticOrder(s))
       cout << "Yes";
    else
       cout << "No";
 
    return 0;
}

// Java implementation of above approach
 
// import  Arrays class
import java.util.Arrays;
 
public class GFG {
 
    // Function that checks whether
    // the string is in alphabetical
    // order or not
    static boolean isAlphabaticOrder(String s)
    {
        // length of the string
        int n = s.length();
       
        // create a character array
        // of the length of the string
        char c[] = new char [n];
       
        // assign the string
        // to character array
        for (int i = 0; i < n; i++) {
            c[i] = s.charAt(i);
        }
       
        // sort the character array
        Arrays.sort(c);
       
        // check if the character array
        // is equal to the string or not
        for (int i = 0; i < n; i++)
            if (c[i] != s.charAt(i)) 
                return false;
               
        return true;    
    }
     
    public static void main(String args[])
    {
        String s = "aabbbcc";
         
        // check whether the string is
        // in alphabetical order or not
        if (isAlphabaticOrder(s))
           System.out.println("Yes");
        else
            System.out.println("No");
           
    }
    // This Code is contributed by ANKITRAI1
}

# Python 3 implementation of above approach
 
# Function that checks whether
# the string is in alphabetical
# order or not
def isAlphabaticOrder(s):
     
    # length of the string
    n = len(s)
 
    # create a character array
    # of the length of the string
    c = [s[i] for i in range(len(s))]
 
    # sort the character array
    c.sort(reverse = False)
 
    # check if the character array
    # is equal to the string or not
    for i in range(n):
        if (c[i] != s[i]):
            return False
         
    return True
 
# Driver code
if __name__ == '__main__':
    s = "aabbbcc"
 
    # check whether the string is
    # in alphabetical order or not
    if (isAlphabaticOrder(s)):
        print("Yes")
    else:
        print("No")
 
# This code is contributed by
# Surendra_Gangwar

// C# implementation of above approach
// import Arrays class
 
using System;
 
public class GFG{
     
    // Function that checks whether
    // the string is in alphabetical
    // order or not
    static bool isAlphabaticOrder(String s)
    {
        // length of the string
        int n = s.Length;
     
        // create a character array
        // of the length of the string
        char []c = new char [n];
     
        // assign the string
        // to character array
        for (int i = 0; i < n; i++) {
            c[i] = s[i];
        }
     
        // sort the character array
        Array.Sort(c);
     
        // check if the character array
        // is equal to the string or not
        for (int i = 0; i < n; i++)
            if (c[i] != s[i])
                return false;
             
        return true;    
    }
     
    static public void Main (){
        String s = "aabbbcc";
         
        // check whether the string is
        // in alphabetical order or not
        if (isAlphabaticOrder(s))
        Console.WriteLine("Yes");
        else
            Console.WriteLine("No");
         
    }
}

<?php
// PHP implementation of above approach
 
// Function that checks whether
// the string is in alphabetical
// order or not
Function isAlphabaticOrder($s)
{
     
    // length of the string
    $n = strlen($s);
 
    $c = array();
     
    // assign the string
    // to character array
    for ($i = 0; $i < $n; $i++)
    {
        $c[$i] = $s[$i];
    }
 
    // sort the character array
    sort($c);
 
    // check if the character array
    // is equal to the string or not
    for ($i = 0; $i < $n; $i++)
        if ($c[$i] != $s[$i])
            return false;
         
    return true;
}
 
// Driver code
$s = "aabbbcc";
 
// check whether the string is
// in alphabetical order or not
if (isAlphabaticOrder($s))
    echo "Yes";
else
    echo "No";
     
// This Code is contributed
// by Shivi_Aggarwal
?>

<script>
//Javascript implementation of above approach
 
// Function that checks whether
// the string is in alphabetical
// order or not
function isAlphabaticOrder(s)
{
    // length of the string
    var n = s.length;
 
    // create a character array
    // of the length of the string
    var c = new Array(n);
 
    // assign the string
    // to character array
    for (var i = 0; i < n; i++) {
        c[i] = s[i];
    }
 
    // sort the character array
    c.sort();
 
    // check if the character array
    // is equal to the string or not
    for (var i = 0; i < n; i++)
        if (c[i] != s[i])
            return false;
         
    return true;   
}
 
s = "aabbbcc";
 
// check whether the string is
// in alphabetical order or not
if (isAlphabaticOrder(s))
  document.write( "Yes");
else
  document.write( "No");
 
//This code is contributed by SoumikMondal
</script>

Yes

Complejidad del tiempo: O(N*log(N))

Espacio Auxiliar: O(N)
Aproximación Eficiente: 

• Ejecute un ciclo de 1 a (n-1) (donde n es la longitud de la string)
• Compruebe si el elemento en el índice ‘i’ es menor que el elemento en el índice ‘i-1’.
• En caso afirmativo, escriba ‘En orden alfabético’.
• Imprima ‘No en orden alfabético’ de lo contrario.

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

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that checks whether
// the string is in alphabetical
// order or not
bool isAlphabaticOrder(string s)
{
    int n = s.length();
 
    for (int i = 1; i < n; i++) {
 
        // if element at index 'i' is less
        // than the element at index 'i-1'
        // then the string is not sorted
        if (s[i] < s[i - 1])
           return false;
    }
 
    return true;
}
 
// Driver code
int main()
{
    string s = "aabbbcc";
 
    // check whether the string is
    // in alphabetical order or not
    if (isAlphabaticOrder(s))
       cout << "Yes";
    else
       cout << "No";
 
    return 0;
}

// Java implementation of above approach
public class GFG {
 
// Function that checks whether
// the string is in alphabetical
// order or not
    static boolean isAlphabaticOrder(String s) {
        int n = s.length();
 
        for (int i = 1; i < n; i++) {
 
            // if element at index 'i' is less
            // than the element at index 'i-1'
            // then the string is not sorted
            if (s.charAt(i) < s.charAt(i - 1)) {
                return false;
            }
        }
 
        return true;
    }
 
// Driver code
    static public void main(String[] args) {
        String s = "aabbbcc";
        // check whether the string is
        // in alphabetical order or not
        if (isAlphabaticOrder(s)) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}
//This code is contributed by PrinciRaj1992

# Python 3 implementation of above approach
 
# Function that checks whether
# the string is in alphabetical
# order or not
def isAlphabaticOrder(s):
 
    n = len(s)
 
    for i in range(1, n):
 
        # if element at index 'i' is less
        # than the element at index 'i-1'
        # then the string is not sorted
        if (s[i] < s[i - 1]) :
            return False
 
    return True
 
# Driver code
if __name__ == "__main__":
 
    s = "aabbbcc"
 
    # check whether the string is
    # in alphabetical order or not
    if (isAlphabaticOrder(s)):
        print("Yes")
    else:
        print("No")

// C# implementation of above approach
using System;
 
public class GFG{
     
// Function that checks whether
// the string is in alphabetical
// order or not
static bool isAlphabaticOrder(string s)
{
    int n = s.Length;
 
    for (int i = 1; i < n; i++) {
 
        // if element at index 'i' is less
        // than the element at index 'i-1'
        // then the string is not sorted
        if (s[i] < s[i - 1])
        return false;
    }
 
    return true;
}
 
// Driver code
    static public void Main (){
    string s = "aabbbcc";
    // check whether the string is
    // in alphabetical order or not
    if (isAlphabaticOrder(s))
    Console.WriteLine ("Yes");
        else
    Console.WriteLine  ("No");
    }
}

<?php
// PHP implementation of above approach
 
// Function that checks whether
// the string is in alphabetical
// order or not
function isAlphabaticOrder($s)
{
    $n = strlen($s);
    for ($i = 1; $i < $n; $i++)
    {
 
        // if element at index 'i' is less
        // than the element at index 'i-1'
        // then the string is not sorted
        if ($s[$i] < $s[$i - 1])
        return false;
    }
 
    return true;
}
 
// Driver code
$s = "aabbbcc";
 
// check whether the string is
// in alphabetical order or not
if (isAlphabaticOrder($s))
    echo "Yes";
else
    echo "No";
 
// This code is contributed
// by Sach_Code
?>

<script>
// JavaScript implementation of above approach
 
// Function that checks whether
// the string is in alphabetical
// order or not
function isAlphabaticOrder( s){
    let n = s.length;
 
    for (let i = 1; i < n; i++) {
        // if element at index 'i' is less
        // than the element at index 'i-1'
        // then the string is not sorted
        if (s[i] < s[i - 1])
           return false;
    }
    return true;
}
 
// Driver code
let s = "aabbbcc";
// check whether the string is
// in alphabetical order or not
if (isAlphabaticOrder(s))
    document.write("Yes");
else
    document.write("No");
</script>

Yes

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

Otro enfoque eficiente:

Los pasos involucrados son los siguientes:

• Itere a través de la string dada y almacene el conteo de frecuencia de cada alfabeto.
• Luego itere a través de cada alfabeto en orden lexicográfico creciente (de la a a la z) y deje que el conteo de cualquier alfabeto sea x. Luego verifique si exactamente x elementos están presentes en la string dada en orden continuo o no.
• Si coincide con todos los alfabetos, devuelve verdadero; de lo contrario, devuelve falso.

Ejemplo ilustrativo:

Sea Str=”aabbccb”

Luego, el recuento de cada alfabeto es el siguiente { a = 2, b = 3 y c = 2}. 

Ahora iteraremos a través de cada alfabeto y verificaremos la condición.

Como a=2, los primeros 2 elementos de la string deben ser ‘a’. Dado que hay 2 elementos con ‘a’ en la string dada, avanzaremos más.

Ahora b = 3, por lo que los siguientes 3 elementos deben ser ‘b’ en la string, que no está allí ya que el quinto elemento en la string dada no es ‘b’. Por lo tanto, la string no está en orden alfabético.

A continuación se muestra el código para el enfoque anterior:

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that checks whether
// the string is in alphabetical
// order or not
bool isAlphabaticOrder(string s)
{
    // array to store the
    // count of each alphabet
    int arr[26]={0};
     
    int n = s.length();
     
    for(int i=0;i<n;i++)
    {
        arr[s[i]-'a']++;
    }
     
    int ind=0;
    // Using the count array we will iterate
    // in lexicographic order through each
    // alphabet present and check if the
    // string has element present in same
    // order or not
    for(int i=0;i<26;i++)
    {
        while(arr[i]--)
        {
            char c= char(97+i);
            if(c!=s[ind])
            {
                return false;
            }
            else
            {
                ind++;
            }
             
        }
    }
 
    return true;
}
 
// Driver code
int main()
{
    string s = "aabbbcc";
 
    // check whether the string is
    // in alphabetical order or not
    if (isAlphabaticOrder(s))
    cout << "Yes";
    else
    cout << "No";
 
    return 0;
}
 
// This code is contributed by Pushpesh Raj.

Yes

Complejidad de tiempo: O(N)
Espacio auxiliar: O(1) ya que la array utilizada para contar la frecuencia de los alfabetos es de tamaño constante.