Zigzag String Sort: Alternating Characters for a Perfect Reorder
Intuition\nThe intuition behind this approach is to reorder the string by repeatedly picking the smallest and largest characters in alternating fashion. We trac
# Intuition\nThe intuition behind this approach is to reorder the string by repeatedly picking the smallest and largest characters in alternating fashion. We track the frequency of each character using a Map and ensure that as we build the result string, we always append characters in the required order until all characters are used up. This method ensures the string is constructed according to the specific rules given in the problem, maintaining order and handling character frequency efficiently.\n\n# Approach\nCount the frequency of each character.\nLoop over all character from \'a\' to \'z\' and append the character if it exists and decrease frequency by 1. Do the same from \'z\' to \'a\'.\nKeep repeating until the frequency of all characters is zero.\n\n# Complexity\n- Time complexity:\nO(NLogN)\n\n- Space complexity:\nO(N)\n\n# Code\n```java []\nclass Solution {\n    public String sortString(String s) {\n        // Convert string to char array\n        char[] arr = s.toCharArray();\n        // Map to store the frequency of each character\n        Map<Character, Integer> freqMap = new HashMap<>();\n        \n        // Fill the map with the frequency of each character\n        for (char ch : arr) {\n            freqMap.put(ch, freqMap.getOrDefault(ch, 0) + 1);\n        }\n        \n        StringBuilder result = new StringBuilder();\n        \n        // Sorted list of unique characters\n        List<Character> characters = new ArrayList<>(freqMap.keySet());\n        Collections.sort(characters);\n\n        while (!freqMap.isEmpty()) {\n            // Step 1 to 3: Pick smallest character and move upwards\n            for (char ch : characters) {\n                if (freqMap.containsKey(ch)) {\n                    result.append(ch);\n                    int count = freqMap.get(ch) - 1;\n                    if (count == 0) {\n                        freqMap.remove(ch);\n                    } else {\n                        freqMap.put(ch, count);\n                    }\n                }\n            }\n\n            // Step 4 to 6: Pick largest character and move downwards\n            for (int i = characters.size() - 1; i >= 0; i--) {\n                char ch = characters.get(i);\n                if (freqMap.containsKey(ch)) {\n                    result.append(ch);\n                    int count = freqMap.get(ch) - 1;\n                    if (count == 0) {\n                        freqMap.remove(ch);\n                    } else {\n                        freqMap.put(ch, count);\n                    }\n                }\n            }\n        }\n        \n        return result.toString();\n    }\n}\n```
['Java']