Skip to content

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

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
 public:
  bool isDecomposable(string s) {
    int twos = 0;
    int groupLength = 0;
    char letter = '@';  // the running letter

    for (const char c : s)
      if (c == letter) {
        ++groupLength;
      } else {
        if (groupLength % 3 == 1)
          return false;
        if (groupLength % 3 == 2 && ++twos > 1)
          return false;
        groupLength = 1;
        letter = c;
      }

    // Check the final group.
    if (groupLength % 3 == 1)
      return false;
    if (groupLength % 3 == 2 && ++twos > 1)
      return false;
    return twos == 1;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  public boolean isDecomposable(String s) {
    int twos = 0;
    int groupLength = 0;
    char letter = '@'; // the running letter

    for (final char c : s.toCharArray())
      if (c == letter) {
        ++groupLength;
      } else {
        if (groupLength % 3 == 1)
          return false;
        if (groupLength % 3 == 2 && ++twos > 1)
          return false;
        groupLength = 1;
        letter = c;
      }

    // Check the final group.
    if (groupLength % 3 == 1)
      return false;
    if (groupLength % 3 == 2 && ++twos > 1)
      return false;
    return twos == 1;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
  def isDecomposable(self, s: str) -> bool:
    twos = 0

    for _, group in itertools.groupby(s):
      groupLength = len(list(group))
      if groupLength % 3 == 1:
        return False
      if groupLength % 3 == 2:
        twos += 1
        if twos > 1:
          return False

    return twos == 1