Find Valid Pair of Adjacent Digits in String

Difficulty: Easy | Acceptance: 60.90% | Paid: No Topics: Hash Table, String, Counting

You are given a string num representing a large integer. A pair of adjacent digits in num is called valid if the sum of the two digits equals 10.

Return the resulting string after removing the first occurrence of a valid pair from num. If no such pair exists, return num.

• Examples
• Constraints
• Linear Scan
• Regular Expression

Examples

Example 1:

Input: num = "343"
Output: "343"
Explanation: There is no valid pair of adjacent digits summing to 10.

Example 2:

Input: num = "191"
Output: "1"
Explanation: The first valid pair is "19" (1 + 9 = 10). Removing "19" results in "1".

Example 3:

Input: num = "55"
Output: ""
Explanation: The valid pair is "55" (5 + 5 = 10). Removing "55" results in an empty string.

Constraints

2 <= num.length <= 100
num consists only of digits.
num does not have leading zeros.

Linear Scan

Intuition We iterate through the string once, checking every adjacent pair of digits. The first pair we encounter that sums to 10 is the one we must remove. We then construct a new string excluding these two characters.

Steps

• Iterate through the string from index 0 to length - 2.
• At each index i, convert the characters num[i] and num[i+1] to integers.
• Check if their sum equals 10.
• If it does, return the substring formed by concatenating the part before i and the part after i+2.
• If the loop completes without finding a valid pair, return the original string.

class Solution:
    def findValidPair(self, num: str) -> str:
        for i in range(len(num) - 1):
            if int(num[i]) + int(num[i+1]) == 10:
                return num[:i] + num[i+2:]
        return num

Complexity

• Time: O(n), where n is the length of the string. We traverse the string at most once.
• Space: O(n) to store the resulting string (or O(1) auxiliary space if modifying in-place, though strings are often immutable).
• Notes: This is the most efficient approach for this specific problem.

Regular Expression

Intuition We can define a pattern that matches any two adjacent digits summing to 10. Using a regular expression engine, we can search for the first occurrence of this pattern and replace it with an empty string.

Steps

• Construct a regex pattern that matches all possible pairs summing to 10: (19|28|37|46|55|64|73|82|91).
• Apply the regex replacement to the input string, replacing only the first match.
• Return the modified string.

import re

class Solution:
    def findValidPair(self, num: str) -> str:
        pattern = r"(19|28|37|46|55|64|73|82|91)"
        return re.sub(pattern, "", num, 1)

Complexity

• Time: O(n), as the regex engine scans the string.
• Space: O(n), for the regex pattern compilation and the resulting string.
• Notes: While concise, this approach has higher constant overhead compared to a simple linear scan.