Question

1933. Check if String Is Decomposable Into Value-Equal Substrings

中文文档

Description

A value-equal string is a string where all characters are the same.

• For example, "1111" and "33" are value-equal strings.
• In contrast, "123" is not a value-equal string.

Given a digit string s, decompose the string into some number of consecutive value-equal substrings where exactly one substring has a length of 2 and the remaining substrings have a length of 3.

Return true_ if you can decompose _s_ according to the above rules. Otherwise, return _false.

A substring is a contiguous sequence of characters in a string.

 

Example 1:

Input: s = "000111000"
Output: false
Explanation: s cannot be decomposed according to the rules because ["000", "111", "000"] does not have a substring of length 2.

Example 2:

Input: s = "00011111222"
Output: true
Explanation: s can be decomposed into ["000", "111", "11", "222"].

Example 3:

Input: s = "011100022233"
Output: false
Explanation: s cannot be decomposed according to the rules because of the first '0'.

 

Constraints:

• 1 <= s.length <= 1000
• s consists of only digits '0' through '9'.

Solutions

Solution 1: Two Pointers

We traverse the string $s$, using two pointers $i$ and $j$ to count the length of each equal substring. If the length modulo $3$ is $1$, it means that the length of this substring does not meet the requirements, so we return false. If the length modulo $3$ is $2$, it means that a substring of length $2$ has appeared. If a substring of length $2$ has appeared before, return false, otherwise assign the value of $j$ to $i$ and continue to traverse.

After the traversal, check whether a substring of length $2$ has appeared. If not, return false, otherwise return true.

The time complexity is $O(n)$, where $n$ is the length of the string $s$. The space complexity is $O(1)$.

class Solution:
  def isDecomposable(self, s: str) -> bool:
    i, n = 0, len(s)
    cnt2 = 0
    while i < n:
      j = i
      while j < n and s[j] == s[i]:
        j += 1
      if (j - i) % 3 == 1:
        return False
      cnt2 += (j - i) % 3 == 2
      if cnt2 > 1:
        return False
      i = j
    return cnt2 == 1

class Solution {
  public boolean isDecomposable(String s) {
    int i = 0, n = s.length();
    int cnt2 = 0;
    while (i < n) {
      int j = i;
      while (j < n && s.charAt(j) == s.charAt(i)) {
        ++j;
      }
      if ((j - i) % 3 == 1) {
        return false;
      }
      if ((j - i) % 3 == 2 && ++cnt2 > 1) {
        return false;
      }
      i = j;
    }
    return cnt2 == 1;
  }
}

class Solution {
public:
  bool isDecomposable(string s) {
    int cnt2 = 0;
    for (int i = 0, n = s.size(); i < n;) {
      int j = i;
      while (j < n && s[j] == s[i]) {
        ++j;
      }
      if ((j - i) % 3 == 1) {
        return false;
      }
      cnt2 += (j - i) % 3 == 2;
      if (cnt2 > 1) {
        return false;
      }
      i = j;
    }
    return cnt2 == 1;
  }
};

func isDecomposable(s string) bool {
  i, n := 0, len(s)
  cnt2 := 0
  for i < n {
    j := i
    for j < n && s[j] == s[i] {
      j++
    }
    if (j-i)%3 == 1 {
      return false
    }
    if (j-i)%3 == 2 {
      cnt2++
      if cnt2 > 1 {
        return false
      }
    }
    i = j
  }
  return cnt2 == 1
}

function isDecomposable(s: string): boolean {
  const n = s.length;
  let cnt2 = 0;
  for (let i = 0; i < n; ) {
    let j = i;
    while (j < n && s[j] === s[i]) {
      ++j;
    }
    if ((j - i) % 3 === 1) {
      return false;
    }
    if ((j - i) % 3 === 2 && ++cnt2 > 1) {
      return false;
    }
    i = j;
  }
  return cnt2 === 1;
}

Solution 2

class Solution:
  def isDecomposable(self, s: str) -> bool:
    cnt2 = 0
    for _, g in groupby(s):
      m = len(list(g))
      if m % 3 == 1:
        return False
      cnt2 += m % 3 == 2
      if cnt2 > 1:
        return False
    return cnt2 == 1