We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Valid Pair of Adjacent Digits in String

Number: 3736

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

We are given a string s consisting only of digits from '1' to '9'. We need to find the first adjacent pair in s where:

  • The two digits are different.
  • Each digit in the pair appears in s exactly as many times as its numeric value. Return the valid pair as a string, or return an empty string if no valid pair exists.

Key Insights

  • Use a hash table (frequency map) to count the frequency of each digit in s.
  • Iterate through the string examining each adjacent pair.
  • For each pair, check if:
    • The digits are distinct.
    • Frequency of the first digit equals its numeric value.
    • Frequency of the second digit equals its numeric value.
  • Return the first pair satisfying these conditions.

Space and Time Complexity

Time Complexity: O(n), where n is the length of s (we traverse the string to build the frequency map and again to find the pair).
Space Complexity: O(1), since the frequency map will only store counts for digits '1' to '9' (constant size).

Solution

We first build a frequency table for all digits in s. Then, we scan through s checking each adjacent pair. For each pair, we verify that they are not equal and that each digit’s frequency matches the numeric value of the digit. If such a pair is found, we return it immediately. Otherwise, if no valid pair is found, we return an empty string.

Code Solutions

# Function to find the valid adjacent pair
def find_valid_pair(s):
    # Build frequency dictionary for digits in s
    frequency = {}
    for ch in s:
        frequency[ch] = frequency.get(ch, 0) + 1

    # Iterate through adjacent pairs in the string
    for i in range(len(s) - 1):
        first, second = s[i], s[i+1]
        # Check that the two digits are different
        if first == second:
            continue
        # Check if each digit's frequency equals its numeric value
        if frequency[first] == int(first) and frequency[second] == int(second):
            return first + second
    return ""

# Example usage
print(find_valid_pair("2523533"))  # Expected output: "23"
← Back to All Questions