1370. Increasing Decreasing String

public class Solution {
    public string SortString(string s) {
        int[] charCount = new int[26];
        foreach (char c in s) {
            charCount[c - 'a']++;
        }
        
        var result = new System.Text.StringBuilder();
        while (result.Length < s.Length) {
            for (char c = 'a'; c <= 'z'; c++) {
                if (charCount[c - 'a'] > 0) {
                    result.Append(c);
                    charCount[c - 'a']--;
                }
            }
            for (char c = 'z'; c >= 'a'; c--) {
                if (charCount[c - 'a'] > 0) {
                    result.Append(c);
                    charCount[c - 'a']--;
                }
            }
        }
        
        return result.ToString();
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public string SortString(string s) {
        vector<int>& charCount = new int[26];
        foreach (char c in s) {
            charCount[c - 'a']++;
        }
        
        var result = new System.Text.StringBuilder();
        while (result.size() < s.size()) {
            for (char c = 'a'; c <= 'z'; c++) {
                if (charCount[c - 'a'] > 0) {
                    result.Append(c);
                    charCount[c - 'a']--;
                }
            }
            for (char c = 'z'; c >= 'a'; c--) {
                if (charCount[c - 'a'] > 0) {
                    result.Append(c);
                    charCount[c - 'a']--;
                }
            }
        }
        
        return result.ToString();
    }
}

import java.util.*;

public class Solution {
    public String sortString(String s) {
        int[] charCount = new int[26];
        for (char c : s.toCharArray()) {
            charCount[c - 'a']++;
        }
        
        StringBuilder result = new StringBuilder();
        while (result.length() < s.length()) {
            for (char c = 'a'; c <= 'z'; c++) {
                if (charCount[c - 'a'] > 0) {
                    result.append(c);
                    charCount[c - 'a']--;
                }
            }
            for (char c = 'z'; c >= 'a'; c--) {
                if (charCount[c - 'a'] > 0) {
                    result.append(c);
                    charCount[c - 'a']--;
                }
            }
        }
        
        return result.toString();
    }
}

class Solution:
    def sortString(self, s: str) -> str:
        from collections import Counter
        char_count = Counter(s)
        result = []
        
        while len(result) < len(s):
            for char in "abcdefghijklmnopqrstuvwxyz":
                if char_count[char] > 0:
                    result.append(char)
                    char_count[char] -= 1
            for char in "zyxwvutsrqponmlkjihgfedcba":
                if char_count[char] > 0:
                    result.append(char)
                    char_count[char] -= 1
        
        return ''.join(result)

func sortString(s string) string {
    charCount := make([]int, 26)
    for _, c := range s {
        charCount[c - 'a']++
    }
    
    result := make([]byte, 0, len(s))
    for len(result) < len(s) {
        for c := byte('a'); c <= 'z'; c++ {
            if charCount[c - 'a'] > 0 {
                result = append(result, c)
                charCount[c - 'a']--
            }
        }
        for c := byte('z'); c >= 'a'; c-- {
            if charCount[c - 'a'] > 0 {
                result = append(result, c)
                charCount[c - 'a']--
            }
        }
    }
    
    return string(result)
}

Explanation

Algorithm

Выберите наименьший символ из s и добавьте его к результату.

Выберите наименьший символ из s, который больше последнего добавленного символа, и добавьте его.

Повторяйте шаг 2, пока не сможете выбрать больше символов.

Выберите наибольший символ из s и добавьте его к результату.

Выберите наибольший символ из s, который меньше последнего добавленного символа, и добавьте его.

Повторяйте шаг 5, пока не сможете выбрать больше символов.

Повторяйте шаги с 1 по 6, пока не выберете все символы из s.

На каждом этапе, если наименьший или наибольший символ появляется более одного раза, вы можете выбрать любое его вхождение и добавить его к результату.

Верните результирующую строку после сортировки s с помощью этого алгоритма.

Пример

Input: s = "rat"

Output: "art"

Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.

👨‍💻

Алгоритм:

Инициализация и сортировка:

Создайте словарь для подсчета количества каждого символа в строке s. Создайте результирующую строку result.

Перебор и добавление символов:

Используйте два цикла: первый для добавления символов в возрастающем порядке, второй — в убывающем. В каждом цикле добавляйте символы к результату, обновляя их количество в словаре.

Проверка завершения:

Повторяйте шаги 2 и 3, пока не будут добавлены все символы из строки s в result.

😎