HackerRank ‘Weighted Uniform Strings’ Solution

H
Short Problem Definition:

A weighted string is a string of lowercase English letters where each letter has a weight. Character weights are 1 to  26 from a to z…

Link

Weighted Uniform String

Complexity:

time complexity is O(N)

space complexity is O(N)

Execution:

Parsing the string for every query is suboptimal, so I first preprocess the string. Now we know that uniform strings contain the same characters. A string can be of length 1. Do a single pass of the string and create all uniform substrings.

Solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def weightedUniformStrings(s, queries):
    weights = set()
    prev = -1
    length = 0
    for c in s:
        weight = ord(c) - ord('a') + 1
        weights.add(weight)
        if prev == c:
            length += 1
            weights.add(length*weight)
        else:
            prev = c
            length = 1
     
    rval = []
    for q in queries:
        if q in weights:
            rval.append("Yes")
        else:
            rval.append("No")
    return rval

About the author

Add comment

By admin

Mailchaimp

About Me

I like to Code and Love to share the codes.