Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1933.html

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

Level

Easy

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'.

Solution

Since exactly one substring of s has length 2 and the remaining substrings of s have lengths 3, the length of s must have remainder 2 when mod 3. If the remainder is not 2, return false.

Then split s into several substrings, where each substring consists of all same characters, and any two adjacent substrings have different characters. There should be only one substring the length of which has remainder 2 when mod 3, and the remaining substrings must have lengths that are multiples of 3. Otherwise, return false.

If the substrings meet the criteria above, return true.

  • class Solution {
    public boolean isDecomposable(String s) {
        int length = s.length();
        if (length % 3 != 2)
            return false;
        boolean hasTwo = false;
        int count = 1;
        char prev = s.charAt(0);
        for (int i = 1; i < length; i++) {
            char curr = s.charAt(i);
            if (curr == prev)
                count++;
            else {
                int remainder = count % 3;
                if (remainder == 2) {
                    if (!hasTwo)
                        hasTwo = true;
                    else
                        return false;
                } else if (remainder == 1)
                    return false;
                count = 1;
                prev = curr;
            }
        }
        return true;
    }
}

############

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

  • // OJ: https://leetcode.com/problems/check-if-string-is-decomposable-into-value-equal-substrings/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    bool isDecomposable(string s) {
        int N = s.size(), i = 0, cnt = 0;
        while (i < N) {
            int start = i;
            while (i < N && s[i] == s[start]) ++i;
            int r = (i - start) % 3;
            if (r == 0) continue;
            if (r == 1) return false;
            if (++cnt > 1) return false;
        }
        return cnt == 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



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

All Problems

All Solutions