DDSA Solutions

Repeated Pattern Check

Problem Overview

The string may use only the letters x and y, and it is valid when it is a concatenation of blocks of the form x to the n followed by y to the n.

Intuition

The string may use only the letters x and y, and it is valid when it is a concatenation of blocks of the form x to the n followed by y to the n. That means each block is a run of one or more x characters followed immediately by a run of equally many y characters. Walking left to right, count the next run of x, then the following run of y. Those two counts must be positive and equal; then the next block begins. A leading y, a shortfall of y after some x run, or leftover x characters at the end all fail. A plain balance counter that only tracks total x minus y is not enough, because it would accept strings such as xxxyyxyy that are not made of clean x n y n blocks.

Algorithm

  1. 1Start an index at the beginning of the string.
  2. 2While characters remain, count consecutive x characters, then consecutive y characters.
  3. 3Return false when the x count is zero or the two counts differ.
  4. 4Otherwise continue with the next block.
  5. 5Return true after every block succeeds through the end of the string.

Example Walkthrough

Input: s = "xxyyxy"

  1. 1. The first block is xx followed by yy, so both counts are 2 and the block is valid.
  2. 2. The next block is x followed by y, so both counts are 1 and the block is valid.
  3. 3. The string ends with no leftover characters, so the answer is true.

Output: true

Common Pitfalls

  • • Require consecutive runs. Mixing x back in after y has started breaks the current block.
  • • An empty x run before a y run is invalid. The string cannot start a block with y.
  • • Equal total counts of x and y are not enough. The pairing must happen block by block.
  • • After the last valid block there must be nothing left. Trailing x characters alone fail.
Repeated Pattern Check.java
Java
// Approach: The string must be a concatenation of blocks of the form x^n y^n.
// Walk left to right, count each run of x, then the following run of y. The
// two run lengths must match and be positive. Then start the next block.
// Anything left over, or a y before an x, fails.
// Complexity: O(n) time, O(1) extra space.
class Solution {
    public boolean findPattern(String s) {
        int i = 0;
        int n = s.length();

        while (i < n) {
            int xCount = 0;
            int yCount = 0;

            while (i < n && s.charAt(i) == 'x') {
                xCount++;
                i++;
            }
            while (i < n && s.charAt(i) == 'y') {
                yCount++;
                i++;
            }

            if (xCount == 0 || xCount != yCount) {
                return false;
            }
        }
        return true;
    }
}
Was this solution helpful?