最小チワワ問題 [yukicoder No.345]

yukicoder.me

文字列sの中にある最短のチワワ列を探す問題です。

チワワ列とは、 c,w,w がこの順で含まれている文字列と定義付けられています。正規表現で表すと "c.*w.*w" ですね。

調べたところによると計算量 O(N) で解ける方法もあるみたいですが、私には理解が難しそうだったので、おとなしく普通の方法で解くことにしました。最悪計算量は O(N*(N+1)/2) だと思います。

import java.util.*;

class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		
		String s = sc.next();
		
		int min = Integer.MAX_VALUE;
		for (int i=0; i<s.length(); i++) {
			if (s.charAt(i) == 'c') {
				int wNum = 0;
				for (int j=i; j<s.length(); j++) {
					if (s.charAt(j) == 'w') wNum++;
					if (wNum == 2) {
						min = Math.min(min, j-i+1);
						break;
					}
				}
			}
		}
		
		System.out.println(min==Integer.MAX_VALUE?-1:min);
		
	}
}

文字列から c を見つけるたびにその後ろを探索して、w を合計2個見つけたらチワワ列の完成なので、探索を終わり、その時点での最短チワワ列と長さを比較します。あとはこれを繰り返して、すべての c について探索し終わったら、最短のチワワ列（初期値のまま、すなわちチワワ列が存在しないなら -1 ）を出力して終了です。