Check if the characters of a given string are in alphabetical order
Given a string ‘s’, the task is to find if the characters of the string are in alphabetical order. The string contains only lowercase characters.
Examples:
Input: Str = "aabbbcc" Output: In alphabetical order Input: Str = "aabbbcca" Output: Not in alphabetical order
A simple approach:
- Store the string to a character array and sort the array.
- If the characters in the sorted array are in the same order as the string then print ‘In alphabetical order ‘.
- Print ‘Not in alphabetical order’ otherwise.
Below is the implementation of the above approach :
C++
// 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
// 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 } |
Python3
# 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#
// 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 // 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 ?> |
Javascript
<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
Complexity Analysis:
- Time Complexity: O(N*log(N))
- Auxiliary Space: O(N)
Efficient approach:
- Run a loop from 1 to (n-1) (where n is the length of the string)
- Check whether the element at index ‘i’ is less than the element at index ‘i-1’.
- If yes, then print ‘In alphabetical order ‘.
- Print ‘Not in alphabetical order’ otherwise.
Below is the implementation of the above approach
C++
// 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
// 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
# 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#
// 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 // 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 ?> |
Javascript
<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
Complexity Analysis:
- Time Complexity: O(N)
- Auxiliary Space: O(1)
Another efficient approach:
The steps involved are as follows:
- Iterate through the given string and store the frequency count of each alphabet.
- Then iterate through each alphabet in lexicographically increasing order(from a to z) and let the count of any alphabet be x. Then check if exactly x elements are present in the given string in continuous order or not.
- If it matches with all alphabets then return true otherwise return false.
Illustrative example:
Let Str=”aabbccb”
Then count of each alphabet is as follows { a=2, b= 3 and c=2}.
Now we will iterate through each alphabets and check for the condition.
As a=2, so first 2 elements in the string need to be ‘a’. Since 2 elements with ‘a’ is there in given string we will move further.
Now b=3, so next 3 elements need to be ‘b’ in the string, which is not there as 5th element in given string is not ‘b’. Hence the string is not in alphabetical order.
Below is the code for the above approach:
C++
// 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. |
Java
// Java implementation of above approach import java.util.*; public class GFG { // Function that checks whether // the string is in alphabetical // order or not static boolean isAlphabaticOrder(String s) { // array to store the // count of each alphabet int [] arr = new int [ 26 ]; for ( int i = 0 ; i < 26 ; i++) { arr[i] = 0 ; } int n = s.length(); for ( int i = 0 ; i < n; i++) { arr[s.charAt(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] > 0 ) { char c = ( char )( 97 + i); if (c != s.charAt(ind)) { return false ; } else { ind++; } arr[i]--; } } return true ; } // Driver code public static void main(String args[]) { String s = "aabbbcc" ; // check whether the string is // in alphabetical order or not if (isAlphabaticOrder(s) == true ) System.out.print( "Yes" ); else System.out.print( "No" ); } } // This code is contributed by Samim Hossain Mondal. |
Python3
# Python implementation of above approach # Function that checks whether # the string is in alphabetical # order or not def isAlphabaticOrder(s): # array to store the # count of each alphabet arr = [ 0 ] * 26 ; n = len (s); for i in range ( 0 ,n): arr[ ord (s[i]) - ord ( 'a' )] + = 1 ; 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 i in range ( 0 , 26 ): while (arr[i]> 0 ): c = chr ( 97 + i); if (c! = s[ind]): return False ; else : ind + = 1 ; arr[i] - = 1 ; return True ; # Driver code s = "aabbbcc" ; # check whether the string is # in alphabetical order or not if (isAlphabaticOrder(s)): print ( "Yes" ); else : print ( "No" ); |
C#
// C# implementation of above approach using System; class GFG { // Function that checks whether // the string is in alphabetical // order or not static bool isAlphabaticOrder( string s) { // array to store the // count of each alphabet int [] arr = new int [26]; for ( int i = 0; i < 26; i++) { arr[i] = 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] > 0) { char c = ( char )(97 + i); if (c != s[ind]) { return false ; } else { ind++; } arr[i]--; } } return true ; } // Driver code public static void Main() { string s = "aabbbcc" ; // check whether the string is // in alphabetical order or not if (isAlphabaticOrder(s) == true ) Console.Write( "Yes" ); else Console.Write( "No" ); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
// Javascript implementation of above approach // Function that checks whether // the string is in alphabetical // order or not function isAlphabaticOrder(s) { // array to store the // count of each alphabet let arr= new Array(26).fill(0); let n = s.length; for (let i=0;i<n;i++) { let x=s[i].charCodeAt( '0' )- 'a' .charCodeAt( '0' ); arr[x]++; } let 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 (let i=0;i<26;i++) { while (arr[i]--) { let c = String.fromCharCode(i+97) if (c!=s[ind]) { return false ; } else { ind++; } } } 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" ); |
Yes
Complexity Analysis:
- Time Complexity: O(N)
Auxiliary Space: O(1) as the array used to count the frequency of alphabets is of constant size.
Contact Us