Beautiful Binary String

Question

Online challenge on Hacker Rank.

Alice has a binary string, B, of length n. She thinks a binary string is beautiful if and only if it doesn't contain the substring 010.

In one step, Alice can change a 0 to 1 a (or vice-versa). Count and print the minimum number of steps needed to make Alice see the string as beautiful.

Input Format

The first line contains an integer, n (the length of binary string B). The second line contains a single binary string, B, of length n.

Output Format

Print the minimum number of steps needed to make the string beautiful.

public class Solution {
 private static int countChange(String text, String pattern) {
 int textLen = text.length();
 int patternLen = pattern.length();
 char[] chars = text.toCharArray();
 int count = 0;
 for (int i = 0; i <= textLen - patternLen; i++) {
 int j = 0;
 while (j < patternLen && chars[i+j] == pattern.charAt(j)) {
 j++;
 }
 if (j == patternLen) {
 count++;
 chars[i+2] = '1';
 }
 }
 return count;
 }
 public static void main(String[] args) {
 Scanner in = new Scanner(System.in);
 int n = in.nextInt();
 String B = in.next();
 System.out.println(countChange(B, "010"));
 }
}

• rossum: The Java library has already done a lot of the work for you. Why not use String.indexOf(pattern, n) to find the next occurrence of the pattern. Change n to step along the binary string as each copy of the pattern is found.
• CodeYogi: Understand the intent of doing problems on hackerrank vs daily job.

Answer 1

Generic pattern argument but hardcoded assumptions

It's nice that you added a generic pattern argument, but your code depends on the pattern being "010" here:

 if (j == patternLen) {
 count++;
 chars[i+2] = '1';
 }

Here, you have hardcoded both a 2 and a '1'. Your program would crash if the pattern were shorter than 3 characters and if i were the last index of the array. Also, if the pattern were "101", setting the last character to '1' would not accomplish anything.

It would be better to just skip the rest of the pattern:

 if (j == patternLen) {
 count++;
 i += patternLen - 1;
 }

• CodeYogi: Nice idea, just remember that i would be incremented once more in the for loop.
• JS1: @CodeYogi Thus i += patternLen - 1 and not i += patternLen.