Case-specific Sorting of Strings

JavaView on GFG

Problem Overview

Sort string keeping uppercase in their positions and lowercase in their positions separately.

Intuition

Sort string keeping uppercase in their positions and lowercase in their positions separately.

Algorithm

1Extract uppercase letters and positions, extract lowercase letters and positions. Sort each group. Re-place.

Common Pitfalls

• Two separate sorted sequences. Map back to original case-specific positions. O(n log n).

Case-specific Sorting of Strings.java

Java

// Approach: Separate uppercase and lowercase characters, sort each group, then merge back in original case positions.
// Time: O(n log n) Space: O(n)
class Solution {
    public static String caseSort(String s) {
        int[] upper = new int[26];
        int[] lower = new int[26];
        for (char a : s.toCharArray()) {
            if (a >= 'a' && a <= 'z')
                lower[a - 'a']++;
            else
                upper[a - 'A']++;

        }
        int i = 0;
        int j = 0;
        StringBuilder sb = new StringBuilder();
        for (int k = 0; k < s.length(); k++) {
            char ch = s.charAt(k);
            if (ch >= 'a' && ch <= 'z') {
                while (lower[i] == 0)
                    i++;

                sb.append((char) ('a' + i));
                lower[i]--;
            } else {
                while (upper[j] == 0)
                    j++;

                sb.append((char) ('A' + j));
                upper[j]--;
            }
        }
        
        return sb.toString();
    }
}

Was this solution helpful?