0
\$\begingroup\$

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"));
    }
}
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – rossum Dec 28 '16 at 16:38
  • \$\begingroup\$ Understand the intent of doing problems on hackerrank vs daily job. \$\endgroup\$ – CodeYogi Dec 28 '16 at 16:41
1
\$\begingroup\$

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;
      }
\$\endgroup\$
  • \$\begingroup\$ Nice idea, just remember that i would be incremented once more in the for loop. \$\endgroup\$ – CodeYogi Dec 28 '16 at 13:23
  • \$\begingroup\$ @CodeYogi Thus i += patternLen - 1 and not i += patternLen. \$\endgroup\$ – JS1 Dec 28 '16 at 13:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.