Move Uppercase alphabets to the end of string

Question

Ques: Given a string as input, move all the alphabets in uppercase to the end of the string. Example:

move("Hello World")="ello orldHW"

Problem is: my code doesn't stop at ello orldHW but it continues to

ello orldHW // Expected output   
ello orldWH // What I am actually getting

Code:

public class MoveUppercaseChars {   
    static String testcase1 = "Hello World";

    public static void main(String args[]){
       MoveUppercaseChars testInstance = new MoveUppercaseChars();
       String result = testInstance.move(testcase1);
       System.out.println("Result : "+result);
    }

    public String move(String str){
       int len = str.length();
       char ch;
       for(int i=0; i<len; i++) {
          ch = str.charAt(i);
          if(((int)ch >= 65) && ((int)ch <= 90)) {
             str = str.substring(0, i) + str.substring(i+1, len) + str.charAt(i);
          }         
       }
       return str;
   }    
}

Answer 1

Store the Lower Case characters and Upper Case separately, then, return the concatenation of both:

public class MoveUppercaseChars {   

static String testcase1 = "Hello World";

public static void main(String args[]){
    MoveUppercaseChars testInstance = new MoveUppercaseChars();
    String result = testInstance.move(testcase1);
    System.out.println("Result : "+result);
}

public String move(String str){
    int len = str.length();
    String low = "";
    String cap = "";
    char ch;
    for(int i=0; i<len; i++)
    {
        ch = str.charAt(i);
        if(((int)ch >= 65) && ((int)ch <= 90))
        {
            cap  += ch;
        }   
        else {
            low += ch;
        }
    }
    return low + cap;
}   
}

Answer 2

I'd use an auxilary string buffer to store the Uppercase in the correct order: and even the lower cases too, so you create less String instances.

public String move(String str){
    char ch;
    int len = str.length();
    // we initialize the buffers with the size so they won't have to be increased
    StringBuffer sbUpperCase = new StringBuffer(len+1);
    StringBuffer sbLowerCase = new StringBuffer(len+1);

    for(int i=0; i<len; i++)
    {
        ch = str.charAt(i);

        //if it is an upperCase letter (but only of the normal ones
        if(Character.isUpperCase(ch))
        {
            sbUpperCase.append(ch);
        }   else {
            sbLowerCase.append(ch);
        }        
    }
    return sbLowerCase.append(sbUpperCase).toString();
} 

Edited with an the Eclipse IDE for better formatting and to use Character.isUpperCase(ch) to check if uppercase. On why it is useful to use StringBuffer instead of the + operator between Strings, check this question: Why to use StringBuffer in Java instead of the string concatenation operator

Answer 3

Most simple & smallest code solution:

public String move(String str) {
    return s.replaceAll("[A-Z]+", "") + s.replaceAll("[^A-Z]+", "");
}

Non-Regex based solution:

Using StringBuilder this algorithm can be made very simple:

public String move(String str){
    StringBuilder sb = new StringBuilder(str);
    int d=0;
    for(int i=0; i<str.length(); i++) {
        int ch = str.charAt(i);
        if(ch >= 65 && ch <= 90) {
            sb.deleteCharAt(i-d++).append((char)ch);
        }           
    }
    return sb.toString();
}  

This will be much more efficient also as compared to manipulating immutable String objects multiple times.

Answer 4

Change your loop to start at the end of the string, and then work backwards. Also, use an array of char[], it will be faster than building a new String in each iteration of the loop. Something like:

EDIT: This is possibly the most efficient way of doing it:

    char[] input = str.toCharArray();
    int c = input.length; // cursor to start at
    int ip = input.length - 1; // insertion point of next UP character.
    while (c > 0) {
        c--;
        if (Character.isUpperCase(input[c])) {
            char tmp = input[c];
            System.arraycopy(input, c + 1, input, c, ip - c);
            input[ip] = tmp;
            ip--;
        }
    }
    return new String(input);

EDIT: The following loop is not the most efficient...... so moving this code example down.

boolean gotUC=true; // do we have upper-case letters, initialize to true
char[] input = str.toCharArray();
int len = input.length;
while (len > 1 && gotUC) {
    len--;
    int c = len;
    while (c > 0 && !Character.isUpperCase(input[c])) {
       c--;
    }
    if (c >= 0) {
        // move the UC Char to before previous UCase letters....
        char tmp = input[c];
        System.arraycopy(input, c + 1, input, c, len - c);
        input[len] = tmp;
    } else {
        gotUC = false;
    }
}
return new String(input);

Answer 5

The problem is that the word H is getting processed twice and during 2nd processing its getting pushed to the end

You may want to keep track of total UPPER CASE words processed, so that they don't get processed again

Also, you can use Character.isUpperCase(ch) to check if a character is upper case

public class Test {

    public static void main(String[] args){
        System.out.println(move("Hello World"));
    }

    public static int getUpperCaseLetters(String str) {
        int r = 0;
        for(char c : str.toCharArray()) {
            if(Character.isUpperCase(c)) {
                r++;
            }
        }
        return r;
    }

    public static String move(String str){
        int len = str.length();
        char ch;
        int totalUppercase = getUpperCaseLetters(str);
        int processed = 0;
        for(int i=0; i<len && processed < totalUppercase; i++)
        {
            ch = str.charAt(i);
            if(Character.isUpperCase(ch))
            {
                str = str.substring(0, i) + str.substring(i+1, len) + str.charAt(i);                
                System.out.println(str);
                processed++;
            }           
        }
        return str;
    }   
}

Answer 6

public String move(String str) {
    int todo = str.length();
    int i = 0;
    while (i < todo)
    {
        char c = str.charAt(i);
        if (c >= 65 && c <= 90) {
            str = str.substring(0, i) + str.substring(i + 1, str.length())
                    + str.charAt(i);
            --todo;
            --i;
        }
        ++i;
    }
    return str;
}

This works without an additional String var. Basic idea: If you put an upper case char to the end of the string, you know that you don't need to go to the end of the string. Therefore the limit is initially str.length() which later decrements.

Also if you find a match you have to check that exact position again (therefore --i). Try "HEllo WOrld" with your code or other code snippets.

Answer 7

I would loop over the input string twice, first copying out the lower-case letters, then copying out the upper-case letters.

public static String move(String str) {
    char[] input = str.toCharArray();
    char[] result = new char[input.length];
    int index = 0;

    for (char current : input)
        if (!Character.isUpperCase(current))
            result[index++] = current;

    for (char current : input)
        if (Character.isUpperCase(current))
            result[index++] = current;

    return new String(result);
}

Answer 8

public class MoveUpperCaseToEnd {

public static void main(String[] args) {
    String string = "SoftwareEngineer";
    String result = moveUpperCase(string);
    System.out.println(result);

}

public static String moveUpperCase(String s) {
    String lowerCase = "";
    String upperCase = "";
    for (int i = 0; i < s.length(); i++) {
        char ch = s.charAt(i);
        if (ch >= 'A' && ch <= 'Z') {
            upperCase += ch;
        } else {
            lowerCase += ch;
        }
    }
    return lowerCase + upperCase;
}

}