Check If Digits Are Equal in String After Operations I

Difficulty: Easy | Acceptance: 82.50% | Paid: No Topics: Math, String, Simulation, Combinatorics, Number Theory

You are given a string s consisting of digits. You can perform the following operation any number of times: Choose an index i (0-indexed) such that 0 < i < s.length and s[i-1] != s[i]. Replace s[i] with s[i-1]. Return true if it is possible to make all characters in s equal after performing the operations, otherwise return false.

• Examples
• Constraints
• Simulation
• Mathematical Proof

Examples

Example 1

Input:

s = "3902"

Output:

true

Explanation: Initially, s = “3902”

First operation:

(s[0] + s[1]) % 10 = (3 + 9) % 10 = 2

(s[1] + s[2]) % 10 = (9 + 0) % 10 = 9

(s[2] + s[3]) % 10 = (0 + 2) % 10 = 2

s becomes “292”

Second operation:

(s[0] + s[1]) % 10 = (2 + 9) % 10 = 1

(s[1] + s[2]) % 10 = (9 + 2) % 10 = 1

s becomes “11”

Since the digits in “11” are the same, the output is true.

Example 2

Input:

s = "34789"

Output:

false

Explanation: Initially, s = “34789”.

After the first operation, s = “7157”.

After the second operation, s = “862”.

After the third operation, s = “48”.

Since ‘4’ != ‘8’, the output is false.

Constraints

1 <= s.length <= 100
s consists of digits.

Simulation

Intuition We can simulate the process of making the string uniform by iterating through the string and applying the operation whenever possible. Since we can perform the operation any number of times, we can propagate the first character to the right.

Steps

• Convert the string to a mutable list of characters.
• Iterate through the string from index 1 to the end.
• If the current character is different from the previous character, replace the current character with the previous one.
• After the loop, check if all characters in the list are the same.

class Solution:
    def isPossibleToMakeEqual(self, s: str) -> bool:
        if not s:
            return True
        s_list = list(s)
        for i in range(1, len(s_list)):
            if s_list[i] != s_list[i-1]:
                s_list[i] = s_list[i-1]
        return all(c == s_list[0] for c in s_list)

Complexity

• Time: O(n) where n is the length of the string.
• Space: O(n) to store the mutable list of characters.
• Notes: This approach directly simulates the problem description and is easy to understand.

Mathematical Proof

Intuition The operation allows us to overwrite any character with the one to its left. By induction, we can overwrite the entire string with the first character. Therefore, it is always possible to make all characters equal.

Steps

• Return true.

class Solution:
    def isPossibleToMakeEqual(self, s: str) -> bool:
        return True

Complexity

• Time: O(1)
• Space: O(1)
• Notes: This is the optimal solution based on the mathematical observation that the first character can always be propagated to the rest of the string.