Leetcode Everyday: 1370. Increasing Decreasing String. Easy

public class Solution {
    public string SortString(string s) {
        var sorted = s.Distinct().OrderBy(x => x).ToList();
        var sortedDesc = sorted.OrderByDescending(x => x).ToList();
        
        var sb = new StringBuilder();
        
        var isAscending = true;
        for (; s.Length > 0; isAscending = !isAscending) { 
            var toSort = isAscending ? sorted : sortedDesc;            
            foreach (var c in toSort) {
                var i = s.IndexOf(c);
                if (i >= 0) {
                    s = s.Remove(i, 1);
                    sb.Append(c);
                }
            }
        }
        
        return sb.ToString();
    }
}

Optimized

public class Solution {
    public string SortString(string s) {
        const int z = 26;
        var freq = new int[z];
        
        var sLength = s.Length;
        var sb = new char[sLength]; // think of this as StringBuilder
        
        foreach (var c in s){
            ++freq[c - 'a'];
        }
        
        for (var i = 0; i < sLength; ){
            
            for (var small = 0; small < z; ++small){
                if (freq[small] > 0){
                    --freq[small];
                    sb[i] = (char)('a' + small);
                    
                    ++i;
                }
            }
            
            for (var large = z - 1; large >= 0; --large){
                if (freq[large] > 0){
                    --freq[large];
                    sb[i] = (char)('a' + large);

                    ++i;
                }
            }
            
        }
        
        return new string(sb);
    }
}

Source: https://leetcode.com/problems/increasing-decreasing-string/submissions/