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
- 1Start an index at the beginning of the string.
- 2While characters remain, count consecutive x characters, then consecutive y characters.
- 3Return false when the x count is zero or the two counts differ.
- 4Otherwise continue with the next block.
- 5Return true after every block succeeds through the end of the string.
Example Walkthrough
Input: s = "xxyyxy"
- 1. The first block is xx followed by yy, so both counts are 2 and the block is valid.
- 2. The next block is x followed by y, so both counts are 1 and the block is valid.
- 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.
// 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;
}
}