import java.util.*;

class Solution {
    static List<String> radixSortMSD(List<String> words) {
        if (words == null) {
            return null;
        }

        return radix(words, 0);
    }

    static LinkedList<String> radix(List<String> words, int index) {
LinkedList<String> res = new LinkedList<>();
        @SuppressWarnings("unchecked")
        LinkedList<String>[] buckets = new LinkedList[26];

        for(int i = 0; i < buckets.length; i++) {
            buckets[i] = new LinkedList<String>();
        }

        for(String w : words) {
            if(w.length() - 1 < index) {
                res.add(w);
            }
        }

        for(String w : words) {
            if(w.length()-1 >= index) {
                int idx = w.charAt(index) - 'a';
                buckets[idx].add(w);
            }
        }

        for(int i = 0; i < buckets.length; i++) {
            if(buckets[i].size() > 0) {
                buckets[i] = radix(buckets[i], index+1);
            }
        }

        for(int i = 0; i < buckets.length; i++) {
            for(String w : buckets[i]) {
                res.add(w);
            }
        }
        return res;
    }
}