<String> 161 358

161. One Edit Distance

1. 两个字符串的长度之差大于1，直接返回False。

2. 两个字符串的长度之差等于1，长的那个字符串去掉一个字符，剩下的应该和短的字符串相同。

3. 两个字符串的长度之差等于0，两个字符串对应位置的字符只能有一处不同。

class Solution {
    public boolean isOneEditDistance(String s, String t) {
        for(int i = 0; i < Math.min(s.length(), t.length()); i++){
            if(s.charAt(i) != t.charAt(i)){
                if(s.length() == t.length()) return s.substring(i + 1).equals(t.substring(i + 1));
                if(s.length() < t.length()) return s.substring(i).equals(t.substring(i + 1));
                else return s.substring(i + 1).equals(t.substring(i));
            }
        }
        return Math.abs(s.length() - t.length()) == 1;
    }
}

358. Rearrange String k Distance Apart

class Solution {
    public String rearrangeString(String s, int k) {
        if(k == 0 || s.length() < k) return s;
        int[] map = new int[26];
        for(char c : s.toCharArray()){
            map[c - 'a']++;
        }
        
        StringBuilder sb = new StringBuilder();
        PriorityQueue<int[]> heap = new PriorityQueue<>(
            (a, b) -> a[1] == b[1] ? a[0] - b[0] : b[1] - a[1]);
        for(int i = 0; i < 26 ; i++){
            if(map[i] > 0){
                heap.offer(new int[]{i, map[i]});
            }
        }
        
        while(!heap.isEmpty()){
            List<Integer> list = new ArrayList<>();
            for(int i = 0; i < k; i++){
                int[] cur = heap.poll();
                sb.append((char)(cur[0] + 'a'));
                list.add(cur[0]);
                
                if(heap.size() == 0){
                    if(i != k - 1 && sb.length() != s.length()) return "";
                    break;
                }
            }
            
            for(int i : list){
                if(--map[i] > 0){
                    heap.offer(new int[]{i, map[i]});
                }
            }
        }
        return sb.toString();
    }
}