LeetCode 3931 - Check Adjacent Digit Differences

Difficulty: 🟢 Easy
Topics: String

Solution

Problem Understanding

The problem asks us to determine whether the absolute difference between every pair of adjacent digits in a given string s is at most 2. The input s is a string of digits, with a minimum length of 2 and a maximum of 100. Each character in the string is guaranteed to be a digit, so we do not need to handle non-digit characters or empty strings.

In simpler terms, we need to check every neighboring pair of digits in the string and verify that the difference between them does not exceed 2. If any pair violates this condition, the output should be false; otherwise, it should be true.

Important observations from the constraints are that the string is relatively short (maximum length 100), so a simple linear scan is sufficient. Edge cases to consider include strings of length 2 (the smallest possible input), strings where all digits are the same, and strings where the first violation occurs at the end.

Approaches

The brute-force approach is straightforward: iterate through every adjacent pair of digits, compute their absolute difference, and check if it exceeds 2. If any difference exceeds 2, return false. Otherwise, return true. Since the string length is small, this approach is actually efficient enough, but it is technically O(n) time.

There is no significant optimization needed because each digit must be checked against its neighbor. The key observation is that we only need a single pass through the string, comparing each character with the next one, making a single linear scan both simple and optimal.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Iterate through adjacent pairs and check differences
Optimal	O(n)	O(1)	Same as brute force, linear scan is sufficient for small n

Algorithm Walkthrough

Convert the input string s into digits implicitly by using character arithmetic. Since s contains only digits, int(s[i]) gives the numeric value of the digit.
Iterate from the first character to the second-to-last character of s using an index i.
For each index i, calculate the absolute difference between s[i] and s[i+1].
If at any point this difference exceeds 2, immediately return false because the condition is violated.
If the loop completes without finding any difference greater than 2, return true as all adjacent pairs satisfy the condition.

Why it works: The invariant is that at each step, we check the condition for the current pair of digits. Since every pair is checked, the algorithm guarantees that the returned result accurately reflects whether all adjacent differences are at most 2.

Python Solution

class Solution:
    def isAdjacentDiffAtMostTwo(self, s: str) -> bool:
        for i in range(len(s) - 1):
            if abs(int(s[i]) - int(s[i + 1])) > 2:
                return False
        return True

This implementation loops through each adjacent pair in the string, computes their absolute difference using abs(int(s[i]) - int(s[i + 1])), and returns False immediately if the difference exceeds 2. If the loop completes, all differences are valid, so it returns True.

Go Solution

func isAdjacentDiffAtMostTwo(s string) bool {
    for i := 0; i < len(s)-1; i++ {
        diff := int(s[i]-'0') - int(s[i+1]-'0')
        if diff < 0 {
            diff = -diff
        }
        if diff > 2 {
            return false
        }
    }
    return true
}

In Go, characters are represented as bytes, so we subtract '0' to convert a digit character to its integer value. The rest of the logic mirrors the Python solution: compute the absolute difference and return false if it exceeds 2.

Worked Examples

Example 1: s = "132"

i	s[i]	s[i+1]	abs(s[i]-s[i+1])	Result
0	1	3	2	valid
1	3	2	1	valid

All differences ≤ 2, return true.

Example 2: s = "129"

i	s[i]	s[i+1]	abs(s[i]-s[i+1])	Result
0	1	2	1	valid
1	2	9	7	invalid

Difference > 2, return false.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We iterate through the string once, comparing each pair of adjacent digits.
Space	O(1)	No extra space is used beyond a few integer variables.

The algorithm is efficient because the string length is bounded by 100, and only a single linear pass is needed.

Test Cases

# provided examples
assert Solution().isAdjacentDiffAtMostTwo("132") == True  # differences are 2 and 1
assert Solution().isAdjacentDiffAtMostTwo("129") == False # difference 7 > 2

# edge cases
assert Solution().isAdjacentDiffAtMostTwo("11") == True  # all digits same
assert Solution().isAdjacentDiffAtMostTwo("12") == True  # smallest length valid
assert Solution().isAdjacentDiffAtMostTwo("10") == False # difference 1-0=1 valid but check
assert Solution().isAdjacentDiffAtMostTwo("2468") == False # differences 2,2,2,4 -> fails at end
assert Solution().isAdjacentDiffAtMostTwo("9876543210") == False # descending differences mostly 1 but ends 1-0=1 valid
assert Solution().isAdjacentDiffAtMostTwo("22222") == True  # all same digits

Test	Why
"132"	Checks normal case with valid differences
"129"	Checks normal case with invalid difference
"11"	Smallest length with identical digits
"12"	Smallest valid difference of 1
"10"	Checks adjacent with boundary difference
"2468"	Multiple differences, last one invalid
"9876543210"	Descending digits, all valid except near edges
"22222"	Repeated identical digits

Edge Cases

One edge case is a string of length 2, such as "12" or "97". Because there is only one adjacent pair, the algorithm must handle this correctly without indexing errors. Our loop goes up to len(s) - 1, which ensures it checks this single pair.

Another edge case is when all digits are the same, e.g., "1111". The differences are all zero, and the algorithm should return true. The implementation naturally handles this because abs(0) is 0, which is ≤ 2.

A third edge case is when the difference exceeding 2 occurs at the end of the string, e.g., "1249". The algorithm must continue checking all pairs until the last, and correctly return false when the last difference fails the condition. This is handled by the for loop which iterates through all adjacent indices.