Taro Logo

Number of Substrings With Fixed Ratio

Medium
Intuit logo
Intuit
0 views
Topics:
StringsArrays

You are given a string s consisting of digits from '1' to '9' and two positive integers num1 and num2.

A substring of s is considered good if its length is divisible by num1 and the ratio of its first num1 characters' numerical product to its last num1 characters' numerical product is equal to num2.

  • For example, if num1 = 2, then a good substring "123456" has a length divisible by 2 and the product of its first 2 characters (1 * 2 = 2) divided by the product of its last 2 characters (5 * 6 = 30) is equal to num2.

Return the number of good substrings of s.

Note that:

  • The product of an empty string is considered equal to 1.
  • The answer may not fit in a 32-bit integer, so you should return it as a 64-bit integer.

Example 1:

Input: s = "2358132", num1 = 1, num2 = 3
Output: 3
Explanation: There are 3 good substrings:
- s[0...0] = "2". Its length is divisible by num1 = 1. The product of its first num1 = 1 characters is 2. The product of its last num1 = 1 characters is 2. The ratio is 2 / 2 = 1 != num2 = 3.
- s[2...2] = "5". Its length is divisible by num1 = 1. The product of its first num1 = 1 characters is 5. The product of its last num1 = 1 characters is 5. The ratio is 5 / 5 = 1 != num2 = 3.
- s[3...3] = "8". Its length is divisible by num1 = 1. The product of its first num1 = 1 characters is 8. The product of its last num1 = 1 characters is 8. The ratio is 8 / 8 = 1 != num2 = 3.
- s[0...1] = "23". Its length is divisible by num1 = 1. The product of its first num1 = 1 characters is 2. The product of its last num1 = 1 characters is 3. The ratio is 2 / 3 != num2 = 3.
- s[0...2] = "235". Its length is divisible by num1 = 1. The product of its first num1 = 1 characters is 2. The product of its last num1 = 1 characters is 5. The ratio is 2 / 5 != num2 = 3.
- s[0...3] = "2358". Its length is divisible by num1 = 1. The product of its first num1 = 1 characters is 2. The product of its last num1 = 1 characters is 8. The ratio is 2 / 8 != num2 = 3.
- s[0...4] = "23581". Its length is divisible by num1 = 1. The product of its first num1 = 1 characters is 2. The product of its last num1 = 1 characters is 1. The ratio is 2 / 1 != num2 = 3.
- s[0...5] = "235813". Its length is divisible by num1 = 1. The product of its first num1 = 1 characters is 2. The product of its last num1 = 1 characters is 3. The ratio is 2 / 3 != num2 = 3.
- s[0...6] = "2358132". Its length is divisible by num1 = 1. The product of its first num1 = 1 characters is 2. The product of its last num1 = 1 characters is 2. The ratio is 2 / 2 = 1 != num2 = 3.
- s[1...1] = "3". Its length is divisible by num1 = 1. The product of its first num1 = 1 characters is 3. The product of its last num1 = 1 characters is 3. The ratio is 3 / 3 = 1 != num2 = 3.
- s[1...2] = "35". Its length is divisible by num1 = 1. The product of its first num1 = 1 characters is 3. The product of its last num1 = 1 characters is 5. The ratio is 3 / 5 != num2 = 3.
- s[1...3] = "358". Its length is divisible by num1 = 1. The product of its first num1 = 1 characters is 3. The product of its last num1 = 1 characters is 8. The ratio is 3 / 8 != num2 = 3.
- s[1...4] = "3581". Its length is divisible by num1 = 1. The product of its first num1 = 1 characters is 3. The product of its last num1 = 1 characters is 1. The ratio is 3 / 1 != num2 = 3.
- s[1...5] = "35813". Its length is divisible by num1 = 1. The product of its first num1 = 1 characters is 3. The product of its last num1 = 1 characters is 3. The ratio is 3 / 3 = 1 != num2 = 3.
- s[1...6] = "358132". Its length is divisible by num1 = 1. The product of its first num1 = 1 characters is 3. The product of its last num1 = 1 characters is 2. The ratio is 3 / 2 != num2 = 3.
- s[2...2] = "5". Its length is divisible by num1 = 1. The product of its first num1 = 1 characters is 5. The product of its last num1 = 1 characters is 5. The ratio is 5 / 5 = 1 != num2 = 3.
- s[2...3] = "58". Its length is divisible by num1 = 1. The product of its first num1 = 1 characters is 5. The product of its last num1 = 1 characters is 8. The ratio is 5 / 8 != num2 = 3.
- s[2...4] = "581". Its length is divisible by num1 = 1. The product of its first num1 = 1 characters is 5. The product of its last num1 = 1 characters is 1. The ratio is 5 / 1 != num2 = 3.
- s[2...5] = "5813". Its length is divisible by num1 = 1. The product of its first num1 = 1 characters is 5. The product of its last num1 = 3. The ratio is 5 / 3 != num2 = 3.
- s[2...6] = "58132". Its length is divisible by num1 = 1. The product of its first num1 = 1 characters is 5. The product of its last num1 = 2. The ratio is 5 / 2 != num2 = 3.
- s[3...3] = "8". Its length is divisible by num1 = 1. The product of its first num1 = 1 characters is 8. The product of its last num1 = 8. The ratio is 8 / 8 = 1 != num2 = 3.
- s[3...4] = "81". Its length is divisible by num1 = 1. The product of its first num1 = 1 characters is 8. The product of its last num1 = 1. The ratio is 8 / 1 != num2 = 3.
- s[3...5] = "813". Its length is divisible by num1 = 1. The product of its first num1 = 1 characters is 8. The product of its last num1 = 3. The ratio is 8 / 3 != num2 = 3.
- s[3...6] = "8132". Its length is divisible by num1 = 1. The product of its first num1 = 1 characters is 8. The product of its last num1 = 2. The ratio is 8 / 2 != num2 = 3.
- s[4...4] = "1". Its length is divisible by num1 = 1. The product of its first num1 = 1 characters is 1. The product of its last num1 = 1. The ratio is 1 / 1 != num2 = 3.
- s[4...5] = "13". Its length is divisible by num1 = 1. The product of its first num1 = 1 characters is 1. The product of its last num1 = 3. The ratio is 1 / 3 != num2 = 3.
- s[4...6] = "132". Its length is divisible by num1 = 1. The product of its first num1 = 1 characters is 1. The product of its last num1 = 2. The ratio is 1 / 2 != num2 = 3.
- s[5...5] = "3". Its length is divisible by num1 = 1. The product of its first num1 = 1 characters is 3. The product of its last num1 = 3. The ratio is 3 / 3 = 1 != num2 = 3.
- s[5...6] = "32". Its length is divisible by num1 = 1. The product of its first num1 = 1 characters is 3. The product of its last num1 = 2. The ratio is 3 / 2 != num2 = 3.
- s[6...6] = "2". Its length is divisible by num1 = 1. The product of its first num1 = 1 characters is 2. The product of its last num1 = 2. The ratio is 2 / 2 = 1 != num2 = 3.

None of the substrings are good.

Example 2:

Input: s = "1326", num1 = 2, num2 = 1
Output: 1
Explanation: There is 1 good substring:
- s[0...3] = "1326". Its length is divisible by num1 = 2. The product of its first num1 = 2 characters is 1 * 3 = 3. The product of its last num1 = 2 characters is 2 * 6 = 12. The ratio is 3 / 12 != num2 = 1.
- s[0...1] = "13". Its length is divisible by num1 = 2 is false
- s[1...2] = "32". Its length is divisible by num1 = 2 is false
- s[2...3] = "26". Its length is divisible by num1 = 2 is false


Substring [0...3] is invalid because 3/12 != 1.

Example 3:

Input: s = "95145", num1 = 1, num2 = 1
Output: 5
Explanation: There are 5 good substrings:
- s[0...0] = "9". Its length is divisible by num1 = 1. The product of its first num1 = 1 characters is 9. The product of its last num1 = 1 characters is 9. The ratio is 9 / 9 = 1 == num2 = 1.
- s[1...1] = "5". Its length is divisible by num1 = 1. The product of its first num1 = 1 characters is 5. The product of its last num1 = 1 characters is 5. The ratio is 5 / 5 = 1 == num2 = 1.
- s[2...2] = "1". Its length is divisible by num1 = 1. The product of its first num1 = 1 characters is 1. The product of its last num1 = 1 characters is 1. The ratio is 1 / 1 = 1 == num2 = 1.
- s[3...3] = "4". Its length is divisible by num1 = 1. The product of its first num1 = 1 characters is 4. The product of its last num1 = 4. The ratio is 4 / 4 = 1 == num2 = 1.
- s[4...4] = "5". Its length is divisible by num1 = 1. The product of its first num1 = 1 characters is 5. The product of its last num1 = 5. The ratio is 5 / 5 = 1 == num2 = 1.

Constraints:

  • 1 <= s.length <= 105
  • s[i] is a digit from '1' to '9'.
  • 1 <= num1 <= s.length / 2
  • 1 <= num2 <= 20

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What are the possible ranges for num1 and num2, and can they be zero or negative?
  2. What is the maximum possible length of the input string s?
  3. Is the substring required to contain at least one occurrence of both num1 and num2, or can it contain only occurrences of num1 (where occurrences of num2 would then be 0)?
  4. If no substrings satisfy the condition, what should I return?
  5. Are num1 and num2 single-digit numbers, or can they be multiple digits?

Brute Force Solution

Approach

We need to find specific sections within a larger piece of text that meet a defined ratio. The brute force strategy checks every possible section to see if it matches the ratio. It's like examining every possible piece of tape from a roll, one by one, to see if its length is correct in relation to its width.

Here's how the algorithm would work step-by-step:

  1. Start with the very first character of the text and consider it as the beginning of a possible section.
  2. Then, extend that section to include the next character, and then the next, and so on, creating sections of increasing length.
  3. For each of these sections, calculate the ratio of how many times one type of character appears to how many times another type of character appears.
  4. See if this calculated ratio matches the ratio we are looking for.
  5. If it does match, make a note of it.
  6. After we have checked all possible sections starting with the first character, move on to the second character of the text and repeat the same process: check sections starting from this second character.
  7. Keep doing this, character by character, until we have checked all possible sections that could exist within the text.
  8. Finally, count how many sections we made a note of, and that's the total number of sections that have the ratio we wanted.

Code Implementation

def number_of_substrings_with_fixed_ratio(main_string, first_character, second_character, required_ratio):
    number_of_substrings = 0

    for start_index in range(len(main_string)): # Iterate through possible start indices

        for end_index in range(start_index, len(main_string)): # Iterate through possible end indices

            substring = main_string[start_index:end_index+1]
            first_character_count = 0
            second_character_count = 0

            for char in substring:
                if char == first_character:
                    first_character_count += 1
                elif char == second_character:
                    second_character_count += 1

            # Avoid division by zero
            if second_character_count == 0:
                if first_character_count == 0 and required_ratio == 0:
                   number_of_substrings += 1
                elif first_character_count > 0 and float('inf') == required_ratio:
                    number_of_substrings +=1
                continue

            current_ratio = first_character_count / second_character_count

            # Key decision point, checks required ratio
            if current_ratio == required_ratio:
                number_of_substrings += 1

    return number_of_substrings
Try it yourself on LeetCodeLeetCode

Big(O) Analysis

Time Complexity
O(n²) – The described brute force approach involves iterating through all possible substrings of the input string of length n. For each starting index, we iterate through all possible ending indices to define a substring. Thus, we have a nested loop structure where the outer loop iterates up to n times and the inner loop iterates up to n times in the worst case. This results in approximately n * n operations. Therefore, the time complexity is O(n²).
Space Complexity
O(1) – The provided solution iterates through substrings and calculates ratios without storing any significant auxiliary data structures. It primarily uses a few constant space variables to track the count of characters and the total count of matching substrings. The space required does not scale with the input string length N, as intermediate substring characters are not stored. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The most efficient solution avoids checking every single substring. It focuses on tracking the counts of two different values and using those counts to quickly identify substrings that match the desired ratio.

Here's how the algorithm would work step-by-step:

  1. Start by figuring out what the ratio means in terms of the two values we're counting.
  2. Go through the string and keep a running count of the first value and the second value up to each point.
  3. For each point in the string, check how many previous points have the counts that satisfy the desired ratio.
  4. The number of previous points that satisfy the ratio tells you how many valid substrings end at the current point.
  5. Add up the number of valid substrings you found at each point to get the total number of valid substrings in the entire string.

Code Implementation

def number_of_substrings_with_fixed_ratio(input_string, ratio_numerator, ratio_denominator):
    running_total = 0
    substring_count = 0
    running_total_counts = {0: 1}

    for character in input_string:
        # Calculate prefix sum based on character
        if character == '1':
            running_total += ratio_denominator
        else:
            running_total -= ratio_numerator

        #If the prefix sum already exists, increment the substring count
        if running_total in running_total_counts:
            substring_count += running_total_counts[running_total]
            running_total_counts[running_total] += 1
        else:
            running_total_counts[running_total] = 1

    return substring_count
Try it yourself on LeetCodeLeetCode

Big(O) Analysis

Time Complexity
O(n) – The algorithm iterates through the string of length n once to calculate prefix counts. Then, for each index in the string (again, n iterations), it accesses a hash map or similar data structure (designed for O(1) access) to find the number of previously seen prefix counts that satisfy the ratio condition. Thus, the dominant operation is the single pass through the string, leading to O(n) time complexity.
Space Complexity
O(N) – The described solution involves keeping a running count of two values and checking how many previous counts satisfy the desired ratio. This typically requires storing the counts encountered at each point in the string in a hash map or an array (implicit data structure). Therefore, the auxiliary space used is proportional to the length of the input string, N, where N is the length of the string. Thus, the space complexity is O(N).

Edge Cases

CaseHow to Handle
Empty string sReturn 0 immediately as no substrings can exist.
num2 is zeroCheck if num2 is zero, if so, either return all substrings with zero occurrences of num1 (if num1 is zero as well) or return 0 (if num1 is non-zero) to avoid division by zero and handle invalid ratios.
String 's' containing only num1Iterate through all possible substring lengths and check the ratio condition, accounting for possible multiple valid substrings.
String 's' containing only num2Iterate through all possible substring lengths and check the ratio condition, accounting for possible multiple valid substrings.
Large string 's' causing potential integer overflow if counts are not handled carefully.Use long or appropriate data types to store the counts to avoid integer overflows.
num1 and num2 are the same value.The condition simplifies to counting substrings where occurrences of num1 are equal to the occurrences of itself, which is every substring containing num1.
String 's' does not contain num1 or num2 at all.If num1 and num2 are not present, and num2 is not zero return 0; otherwise if num2 is 0 check for when num1 is also 0 and if it is, all substrings are valid.
String 's' contains characters that are not num1 or num2.The counts of num1 and num2 should only consider substrings consisting of num1 and num2 values, effectively ignoring other characters.
Taro Footer Icon
Taro Footer Logo
Explore Interview QuestionsGoogle Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Jobs By LevelEntry-Level Software Engineer JobsMid-Level Software Engineer JobsSenior Software Engineer JobsStaff Software Engineer Jobs
Explore TrendingLayoffsPerformance Improvement PlanSystem DesignInterpersonal CommunicationTech Lead
ProductH-1B Visa Salary DatabaseBecome An AffiliateGreat DiscussionsPerksTopics
CompanyBlogPrivacy PolicyTerms & ConditionsSupport
Taro iOS appTaro Android app
LinkedIn IconTwitter IconYouTube Icon
Copyright © Taro