Code Implementation

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

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

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

var isDecomposable = function(s) {
    let n = s.length;
    let i = 0, countThree = 0;
    while (i < n) {
        let j = i;
        while (j < n && s[j] === s[i]) j++;
        let length = j - i;
        if (length % 3 === 1) return false;
        if (length % 3 === 2) countThree++;
        i = j;
    }
    return countThree === 1;
};
      

Problem Description

Given a string s, determine if it can be split into one or more contiguous substrings such that:

• Each substring consists of identical characters (i.e., all characters in a substring are the same).
• Each substring has a length of exactly 3, except for exactly one substring, which must have length 2.
• No substring has length less than 2 or more than 3.
• All characters in the string must be used, and substrings must be contiguous.

Thought Process

The problem is essentially about splitting the string into "blocks" of the same character, where each block must be divided into substrings of length 3 or 2, with only one substring of length 2 allowed overall.

A brute-force approach might try all possible ways to split the string, but that's inefficient. Instead, we can scan the string and count the lengths of consecutive identical characters ("runs" or "groups"). For each group, we check if it can be split into substrings of length 3 or 2, keeping in mind the global constraint of only one length-2 substring.

The key insight is to process each group greedily and track whether we've already used our single allowed length-2 substring. If a group cannot be split accordingly, the answer is immediately false.

Solution Approach

We can solve the problem efficiently by iterating through the string and grouping consecutive identical characters. For each group:

• Let length be the size of the group.
• If length % 3 == 1, it's impossible to split this group into substrings of length 3 or 2 (since only one length-2 substring is allowed in total, not per group). Return false.
• If length % 3 == 2, this group will require one length-2 substring. Increment a counter for length-2 substrings.
• If length % 3 == 0, the group can be split into all length-3 substrings, which is allowed.

After processing all groups, check that exactly one length-2 substring was used (count == 1).

1. Initialize an index i = 0 and a counter count_two = 0.
2. While i < len(s):
   • Find the end of the current group of identical characters.
   • Calculate the group length.
   • Apply the above logic based on length % 3.
3. Return True if count_two == 1, otherwise False.

This approach is efficient because it processes each character only once, and uses simple arithmetic and a single counter.

Example Walkthrough

Let's consider s = "aaabbbc".

• First group: "aaa" (positions 0-2), length = 3. 3 % 3 == 0, so it's valid (all length-3 substrings).
• Second group: "bbb" (positions 3-5), length = 3. 3 % 3 == 0, also valid.
• Third group: "c" (position 6), length = 1. 1 % 3 == 1, which is invalid because we can't have a group of length 1.

The function returns False because the last group cannot be split as required.

Now, for s = "aabbbc":

• "aa" (length 2): requires one length-2 substring (count_two = 1).
• "bbb" (length 3): valid, all length-3 substrings.
• "c" (length 1): invalid, as before.

For s = "aabbbccc":

• "aa" (2): count_two = 1
• "bbb" (3): valid
• "ccc" (3): valid

We used exactly one length-2 substring, and the rest are length-3, so the answer is True.

Time and Space Complexity

Brute-force approach: Trying all possible splits is exponential in the length of s, so it's not practical.

Optimized approach: The solution scans the string once, grouping identical characters and performing O(1) work per group.

• Time Complexity: O(n), where n is the length of s, since every character is checked once.
• Space Complexity: O(1), since only a few counters and variables are used, regardless of input size.

Summary

The problem asks us to partition a string into substrings of either length 3 or 2 (with only one length-2 allowed), where each substring consists of the same character. By grouping consecutive characters and checking the group lengths, we can efficiently decide if such a decomposition is possible. The key insight is that only one group in the entire string can contribute a length-2 substring, and the rest must be divisible into length-3 substrings. This method is both simple and optimal, requiring just a single pass through the string and constant extra space.