Find the weight of consecutive substrings

Question

I encountered this problem during a technical assessment last week. I have no idea what I did wrong.

Given a list of integers of size n, find the number of consecutive substrings that have weights ranging from 1, 2, ..., n. The weight of a substring is the number of distinct integers the string contains. For example, weight('1') = 1, weight('1 1') = 1, weight('2 1') = 2.

When the input string is '1 1 2', the output would be '4 2 0'. n is 3, we need to find the number of substrings with weights 1, 2, and 3. For consecutive substrings that have weight 1, there are 4 substrings: '1', '1', '2', and 1 1'. For consecutive substrings that have weight 2, there are 2 substrings: '1 2', and 1 1 2'. For consecutive substrings that have weight 3, there are 0 substrings.

My Python code can only pass 40% of test cases:

import collections
def substringWeights(s):
    n = len(s)
    substrings = []
    for i in range(n):
        for j in range(i+1, n+1):
            substrings.append(s[i:j])

    weight = collections.defaultdict(int)
    for i in range(1, n+1):
    weight[i] = 0

    for item in substrings:
        weightValue = len(set(item))
        weight[weightValue] += 1
    
    res = weight.values()
    res.sort(reverse = True)
    res = list(map(str, res))
    return ' '.join(res)

Here I first generate all substrings and then calculte the weightValue for each substring and record the number using defaultdict.

Have no idea why I did it wrong. Please help!!! Thanks in advance!

Answer 1

I think you can use the sliding window approach to make the calculation more efficient. For each K-size substring of s where 1 <= K <= len(s), you can create a K-size sliding window starting from index 0 to index K - 1 with a dictionary to keep track of unique character occurrence counts in the window (window in below code), and then iterate through the string (ie 1 - K -> 2 - (K + 1) -> ...), for each iteration, window dictionary minus the first character of the previous window and remove the key if it's zero. That way you can efficiently keep track of the unique character counts for each possible substring of s and update the weight counts as you go

def substringWeights(s):
    weights = [0] * len(s)
    for i in range(1, len(s) + 1):
        window = collections.defaultdict(lambda : 0)
        for j in range(i):
            window[s[j]] += 1
        
        weights[len(window) - 1] += 1

        for j in range(i, len(s)):
            window[s[j - 1]] -= 1
            window[s[j]] += 1
            if window[s[j - 1]] == 0:
                window.pop(s[j - 1])
            weights[len(window) - 1] += 1
    return ' '.join([str(x) for x in weights])

Answer 2

You could build a list of numbers using split and go through all subranges converting the sub range into a set. The length of the set will correspond to the weight of that subrange, which you can use as the index of a resulting list of counts:

def subWeight(s):
    nums   = s.split()
    n      = len(nums)
    result = [0] * n
    for start in range(n):
        for end in range(start+1,n+1):
            result[len(set(nums[start:end]))-1] += 1
    return " ".join(map(str,result))

print(subWeight('1 1 2')) # '4 2 0'