BeautifulStrings.java

import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.stream.IntStream;

class BeautifulStrings {
    private void solve() {
        int _t = in.nextInt();
        while (_t-- > 0) {
            String s = in.next();
            int[][] dp = new int[s.length() + 1][6];
            for (int i = 0; i <= s.length(); ++i) {
                Arrays.fill(dp[i], Integer.MAX_VALUE);
            }
            for (int i = 0, j = 1; i < s.length(); ++i, ++j) {
                if (Math.min(dp[j - 1][2], dp[j - 1][5]) != Integer.MAX_VALUE)
                    dp[j][0] = Math.min(dp[j - 1][2], dp[j - 1][5]) + (s.charAt(i) == 'a' ? 0 : 1);
                else
                    dp[j][0] = i + (s.charAt(i) == 'a' ? 0 : 1);
                if (Math.min(dp[j - 1][0], dp[j - 1][3]) != Integer.MAX_VALUE)
                    dp[j][1] = Math.min(dp[j - 1][0], dp[j - 1][3]) + (s.charAt(i) == 'b' ? 0 : 1);
                if (Math.min(dp[j - 1][1], dp[j - 1][4]) != Integer.MAX_VALUE)
                    dp[j][2] = Math.min(dp[j - 1][1], dp[j - 1][4]) + (s.charAt(i) == 'c' ? 0 : 1);

                if (Math.min(dp[j - 1][0], dp[j - 1][3]) != Integer.MAX_VALUE)
                    dp[j][3] = Math.min(dp[j - 1][0], dp[j - 1][3]) + 1;
                else
                    dp[j][3] = 1;
                if (Math.min(dp[j - 1][1], dp[j - 1][4]) != Integer.MAX_VALUE)
                    dp[j][4] = Math.min(dp[j - 1][1], dp[j - 1][4]) + 1;
                if (Math.min(dp[j - 1][2], dp[j - 1][5]) != Integer.MAX_VALUE)
                    dp[j][5] = Math.min(dp[j - 1][2], dp[j - 1][5]) + 1;
            }
//            out.println(Arrays.deepToString(dp));
            out.println(IntStream.of(dp[s.length()]).min().getAsInt());
        }
    }

    private class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
            st = new StringTokenizer("");
        }

        String next() {
            while (!st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        char nextChar() {
            return next().charAt(0);
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }
        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

    private FastScanner in;
    private PrintWriter out;


    private void run() {
        try {
            in = new FastScanner();
            out = new PrintWriter(new BufferedOutputStream(System.out));
            solve();
        } catch (Exception e) {
            throw e;
        } finally {
            out.close();
        }
    }


    public static void main(String[] arg) {
        new BeautifulStrings().run();
    }
}