Calculate smallest number of letters removed to make remaining word lexicographical?


  • I am looking for a solution to the following problem from a coding test.

    > write a program in Java to Calculate the smallest number of letters that must be removed in order for the letters of the remaining word to be sorted in lexicographical order (abcde…wxyz).

    e.g. For example given “banana” the function should return 3 because we can remove three letters (the first 3rd and 6th) to get the word “aan” which is sorted. Please note that it is not possible to be remove fewer than three letters

    But I'm supposed to find the answer in o(n). Also my answer is failing for the input string "iardiaaznaai"

        public int getSmallestNoletters(String[] args) {
          String longestSubString = "s";
    for (int i = 0; i < str.length(); i++) {
    StringBuilder sbuStr = new StringBuilder();
    for (int j = i + 1; j < str.length(); j++) {
    System.out.println("1: " + sbuStr);
    if (sbuStr.charAt(sbuStr.length() - 1) <= str.charAt(j)) {
    } else if (sbuStr.length() > 1 && sbuStr.charAt(sbuStr.length() - 2) <= str.charAt(j)) {
    sbuStr.deleteCharAt(sbuStr.length() - 1);
    if (sbuStr.length() > longestSubString.length())
    longestSubString = sbuStr.toString();
    int ans = str.length() - longestSubString.length();
    System.out.println("Ans: " + ans);
           return ans;
    17 Mei 2018 14:59

Semua Balasan

  • pooja,

    This looks like a homework assignment you want someone to do for you. Unfortunately you have posted to a forum that deals exclusively with questions/issues about customizing and programming Microsoft Project, a project management application. I suggest you find and re-post to a forum that deals with Java.


    17 Mei 2018 15:33