class Solution {
    public int minNumberOfGeese(String s) {
        char[] quacks = s.toCharArray();

        int count = 0;
        while (find(quacks)) {
            count++;
        }

        // 如果没有找到一只大雁返回-1。
        return count == 0 ? -1 : count;
    }

    public boolean find(char[] arr) {
        // 是否有完整找到至少一个quack
        boolean isFind = false;

        // indexes存q u a c k在原数组中对应的下标
        int[] indexes = new int[5];
        // 下一个应该要找的字母
        char nextNeed = 'q';
        // 遍历原数组
        for (int i = 0; i < arr.length; i++) {
            // 如果存在0, 说明进入过下面第5个分支(当arr[i]==k && nextNeed=='k'时), 直接跳过
            if (arr[i] == 0) continue;

            // 如果遍历到q, 并且正好需要q, 则更新下一个需要的字母为u, 并记录下q的下标
            if (arr[i] == 'q' && nextNeed == 'q') {
                nextNeed = 'u';
                indexes[0] = i;
            }
            // 如果遍历到u, 并且正好需要u, 则更新下一个需要的字母为a, 并记录下u的下标
            else if (arr[i] == 'u' && nextNeed == 'u') {
                nextNeed = 'a';
                indexes[1] = i;
            }
            // 如果遍历到a, 并且正好需要a, 则更新下一个需要的字母为c, 并记录下a的下标
            else if (arr[i] == 'a' && nextNeed == 'a') {
                nextNeed = 'c';
                indexes[2] = i;
            }
            // 如果遍历到c, 并且正好需要c, 则更新下一个需要的字母为k, 并记录下c的下标
            else if (arr[i] == 'c' && nextNeed == 'c') {
                nextNeed = 'k';
                indexes[3] = i;
            }
            // 如果遍历到k, 并且正好需要k, 则更新下一个需要的字母为q, 并记录下k的下标
            // 说明此时已经找到quack5个字母了, 将原数组的对应下标全部更新为0, 并更新isFind为true
            else if (arr[i] == 'k' && nextNeed == 'k') {
                nextNeed = 'q';
                indexes[4] = i;
                for (int index : indexes) arr[index] = 0;
                isFind = true;
            }
        }
        return isFind;
    }
}