Skip to content

Instantly share code, notes, and snippets.

@zsrinivas
Created September 2, 2016 18:19
Show Gist options
  • Save zsrinivas/663b82867056437895bc304d9f03abf3 to your computer and use it in GitHub Desktop.
Save zsrinivas/663b82867056437895bc304d9f03abf3 to your computer and use it in GitHub Desktop.
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();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment