Coding Exercise – Sort Letters by Case (C++)

learn-to-code

Given a string which contains only letters. Sort it by lower case first and upper case second. Example: For “abAcD”, a reasonable answer is “acbAD”. Challenge: You should do it in one-pass and in-place.

C++ Solution

No additional space should be used. We can use two pointers to skip in-place characters from both end, swap them if they are not until they meet in the middle.

The space complexity is O(1) and the time complexity is O(n).

class Solution {
public:
    /*
     * @param chars: The letter array you should sort by Case
     * @return: nothing
     */
    void sortLetters(string &chars) {
        int i = 0, j = chars.length() - 1;
        while (i <= j) {
            // skipping in-place lower characters from the begining
            while ((chars[i] >= 'a') && (chars[i] <= 'z') && i < j) i ++;
            // skipping in-place upper characters from the end
            while ((chars[j] >= 'A') && (chars[j] <= 'Z') && i < j) j --;
            // swap
            auto t = chars[i];
            chars[i] = chars[j];
            chars[j] = t;
            i ++; 
            j --;
        }
    }
};

–EOF (The Ultimate Computing & Technology Blog) —