题目描述：

一群大雁往南飞,给定一个字符串记录地面上的游客听到的大雁叫声,请给出叫声最少由几只大雁发出。

具体的

• 大雁发出的完整叫声为”quack“,因为有多只大雁同一时间嘎嘎作响,所以字符串中可能会混合多个”quack”

• 大雁会依次完整发出”quack”, 即字符串中q,u,a,c,k这5个字母按顺序完整存在才能计数为一只大雁如果不完整或者没有按顺序则不予计数。

• 如果字符串不是由q,u,a,ck字符组合而成,或者没有找到一只大雁,请返回-1

输入描述

一个字符串,包含大雁quack的叫声。1<=字符串长度<=1000,字符串中的字符只有q,u,a,c,k

输出描述

大雁的数量

示例1

输入

quackquack

输出

1 这个输入字符串正好包含两个完整的、连续的 "quack"。一只大雁可以发出这样的声音序列，所以最少需要 1 只大雁。

示例2

输入

qaauucqckk

输出

-1

这个输入字符串中的字符虽然都是 'q'、'u'、'a'、'c'、'k' 中的一个，但是它们的顺序不正确。没有一个完整的 "quack" 序列，因此返回 -1。

示例3

输入

quacqkuackquack

输出

1

这个输入字符串可以被解释为两只大雁的叫声交错：

• 第一只大雁：quack
• 第二只大雁：quackquack
• 第二只大雁发出了两次完整的 "quack"，而第一只大雁只发出了一次。

因此，最少需要 2 只大雁才能产生这样的叫声序列。

输入

qququaauqccauqkkcauqqkcauuqkcaaukccakkck

输出

5

这个输入字符串可以被解释为五只大雁的叫声交错。每只大雁至少完整发出了一次 "quack"。

解题思路

题目要求最少的数量

假设每只大雁叫完 quack 以后，还会就这叫，这样可以使得大雁数量最少

如果序列不符合这个规则则，且发声为 q 说明需要有一只新的大雁的叫声

使用一个数组来记录每只大雁当前叫声的状态。遍历输入字符串，对每个字符进行处理：

• 如果是 'q'，检查是否有空闲的大雁（状态为 0），如果没有，就增加一只新的大雁。
• 对于其他字符，查找是否有大雁正在等待发出这个音。
• 如果找到了匹配的大雁，更新发出下一个字母的下标。
• 如果一只大雁完成了整个 "quack"，将其发声位置重置为 0，表示可以开始新的叫声。

源码

public class GooseQuack {
	static  Input input;
	static {
		input = new Input("quackquack");
		input = new Input("qaauucqcaa");
		input = new Input("quacqkuackquack");
		input = new Input("qququaauqccauqkkcauqqkcauuqkcaaukccakkck");
		input = new Input("quacqkuquacqkacuqkackuack");
	}


	public static void main(String[] args) {
		String string = input.nextLine();

		String quack = "quack";
		int quackLength = quack.length();

		ArrayList<Integer> gooseQuack = new ArrayList<>();
		for (int i = 0; i < string.length(); i++) {
			int waitIndex = quack.indexOf(string.charAt(i));
			if (waitIndex == -1) {
				continue;
			}
			boolean addGoose = true;
			for (int j = 0; j < gooseQuack.size(); j++) {
				if (gooseQuack.get(j) % quackLength == waitIndex) {
					gooseQuack.set(j, gooseQuack.get(j) + 1);
					addGoose = false;
					break;
				}
			}
			if (addGoose && waitIndex == 0) {
				gooseQuack.add(1);
			}
		}
		int count = 0;
		for (int i = 0; i < gooseQuack.size(); i++) {
			if (gooseQuack.get(i) >= quackLength) {
				count++;
			}
		}
		if (count > 0) {
			System.out.println(count);
		} else{
			System.out.println(-1);
		}
	}

}