{x}
blog image

Check if String Is Decomposable Into Value-Equal Substrings

Solution Explanation: Check if String Is Decomposable Into Value-Equal Substrings

This problem asks us to determine if a given string s can be decomposed into consecutive value-equal substrings, where exactly one substring has a length of 2, and the rest have a length of 3. A value-equal string is one containing only the same character.

Approach: Two Pointers (Iterative)

The most efficient approach uses a two-pointer technique. We iterate through the string, keeping track of the length of consecutive value-equal substrings.

  1. Iteration: We use a variable i as the starting pointer and j as the ending pointer for each value-equal substring. The loop continues until i reaches the end of the string.

  2. Substrings: Inside the loop, j iterates until it finds a character different from s[i]. The length of the current substring is j - i.

  3. Length Check:

    • If (j - i) % 3 == 1, the substring length isn't divisible by 3 and there's no way to make it into substrings of length 2 or 3, so we return false.
    • If (j - i) % 3 == 2, we've found a substring of length 2. We maintain a counter cnt2. If cnt2 is already greater than 0 (we've already found a substring of length 2), we return false. Otherwise, we increment cnt2.
    • If (j - i) % 3 == 0, this substring is made up of substrings of length 3 only and is valid.

  4. Update Pointers: After checking the length, we update i to j to move to the next substring.

  5. Final Check: After the loop finishes, if cnt2 is exactly 1, it means we've found exactly one substring of length 2 and the rest are of length 3 or 0, so we return true. Otherwise, we return false.

Time and Space Complexity Analysis

  • Time Complexity: O(n), where n is the length of the string. We iterate through the string once.
  • Space Complexity: O(1). We use a constant amount of extra space to store variables like i, j, and cnt2.

Code Implementations

The code implementations below demonstrate the algorithm in several programming languages. They all follow the same basic logic.

Python

from itertools import groupby
 
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

Java

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;
    }
}

C++

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;
    }
};

JavaScript

/**
 * @param {string} s
 * @return {boolean}
 */
var isDecomposable = function(s) {
    let cnt2 = 0;
    for (let i = 0, n = s.length; i < n; ) {
        let 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;
};

Go

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
}

TypeScript

function isDecomposable(s: string): boolean {
    let cnt2 = 0;
    for (let i = 0, n = s.length; i < n; ) {
        let 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;
}

These code snippets provide functional solutions to the problem, all implementing the two-pointer approach described above. Remember to choose the implementation that best suits your preferred programming language.