print the index of the character where it is out of alphabetical order-CodePudding

I am having trouble understanding an interview question, I am meant to print out the index of the character where it is out of alphabetical order. I do not know how to ascertain the index of a character where it is out of alphabetical order. I wrote the full question below:

Write an algorithm to check if a string is sorted in alphabetical order and print O If it is, if it is not in alphabetical order, then print the index of the character where it is out of alphabetical order.

import java.util.Arrays;
 
public class ArrayAlphabet {
 

    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 class Main extends ArrayAlphabet {

    public static void main(String args[]) {
    
        
        String s = "aadbbbcc";
         
        // check whether the string is
        // in alphabetical order or not
        if (isAlphabaticOrder(s))
           System.out.println("0");
        else
            System.out.println("No");
           
    }
}

CodePudding user response：

The code in the original question already uses char charAt(int index) of the String API. So, step through the String, and use charAt to compare each character to the preceding one.

 public int findOutOfOrder (String str) {
    // returns 0 if characters of str are in order.
    // if not in order, returns position of first out of order character

    int r = 0;

    for (int i = 1; i < str.length();   i) {
        if (str.charAt(i) < str.charAt(i - 1)) {
           r = i;
           break;
        }
    }
    return r;
 }

Since the requirement is to return an index, the return type should be int.

CodePudding user response：

As you traverse the string index by index, you can keep a track of the largest character seen so far. If at any point, you see a character which is lower than seen before, you can return that index.

e.g.

01234
acfbg

start by highest seen = a

index = 0, char = a, highest seen = a, a < a? no. [highest seen = a]
index = 1, char = c, highest seen = a, c < a? no. [highest seen = c]
index = 2, char = f, highest seen = c, f < c? no. [highest seen = f]
index = 3, char = b, highest seen = f, b < f? yes [return index 3]

If you are able to traverse the entire string without finding a violation, that means the string is in alphabetical order.

Time complexity is O(length of string). Space complexity is O(1)