Unique Substrings With Equal Digit Frequency - Leetcode Solution

Problem Statement:

You are given a string s consisting of lowercase letters and digits. Return the number of unique substrings of s that have equal number of occurrences of letters and digits.

Note: A substring is a continuous sequence of characters in a string.

Solution:

The brute force approach to solve this problem would be to find all the substrings of the given string and for each substring, check if the count of digits and letters is the same. If it is the same, update the count of unique substrings. However, this will have a time complexity of O(n^3) due to the nested loops to find substrings, count the digits and letters and then check for equality.

A better approach is to use a hashmap to keep track of the count of letters and digits for each substring. For each character in the string, we can maintain a count of the number of digits and letters seen so far. As soon as a substring with the same count of letters and digits is found, the count of unique substrings can be updated.

Algorithm:

1. Initialize two variables, countLetters and countDigits, as 0
2. Initialize a hashmap, freq, to store the frequency of each substrings with the same count of digits and letters
3. Traverse through the input string s using a for loop
4. For each character in the string, increment the count of digits or letters based on whether the character is a digit or a letter
5. Calculate the difference between the count of digits and the count of letters for the current substring using the variables countDigits and countLetters
6. If the difference between the count of digits and letters is 0, create a key in the hashmap with the current count of digits and letters and increase the frequency count by 1
7. If the difference between the count of digits and letters is already present in the hashmap, then add the frequency of the same and update the hashmap with the new frequency count
8. Return the count of unique substrings

Python Code:

def countEqual(s: str) -> int: """ :type s: str :rtype: int """ countLetters , countDigits, res = 0, 0, 0 freq = {}

# traverse through the input string s
for i in range(len(s)):
    # for each character, check if it is digit or letter
    if s[i].isalpha():
        countLetters += 1
    elif s[i].isdigit():
        countDigits += 1
        
    # calculate the difference between the count of digits and letters for the current substring
    difference = countDigits - countLetters
    
    # check if the current substring has the same count of letters and digits
    if difference == 0:
        # update the count of unique substrings
        res += 1
    
    # check if the same difference already exists in the hashmap freq
    if difference in freq:
        res += freq[difference]
        
    # update the frequency count of substrings with the same count of letters and digits
    freq[difference] = freq.get(difference, 0) + 1
    
return res

Time complexity: O(n) - due to traversal of the input string Space complexity: O(n) - due to the storage of substrings and the hashmap to store frequencies.

1