Maximal Char Requests in a String

Question

I have been trying to deal with this problem set, and I have figured out how to solve it as well. But there is one problem that is Timeout error for some hidden cases, but no wrong answers

PROBLEM STATEMENT

In this challenge, a string and a list of intervals are given. The string consists of English letters only and it can contain both lowercase and uppercase letters.

For two different letters, we say that the first letter is greater than the second letter when the first letter comes later in the alphabet than the second letter ignoring the case of the letters. For example, the letter 'Z' and 't' are greater than the letters 'b' and 'G', while the letters 'B' andd 'b' are equal as case is not considered.

The task is the following. For each given interval, you need to find the count of the greatest letter occurring in the string in that interval, ignoring the case of the letters, so occurrences of, for example, a and A are occurrences of the same letter.

Consider, for example, for the string "AbaBacD". In the interval, [0, 4], the greatest letter is 'b' with count 2.

Input Format

The first line contains integer N, denoting the length of the input string.

The second line contains string S.

The third line contains an integer Q, denoting the number of intervals. Each line of the Q subsequent lines contains two space-separated integers xi and yi, denoting the beginning and the end of ith interval.

Output Format

For each interval, print the count of the greatest letter occurring in the string in that interval.

My Algorithm

1. To lowercase the string
2. Loop through the queries array
3. Get the string from start interval to end interval
4. Find greatest char in the string
5. Count the occurrence, and add it to the array
6. Return the array

My Code

def getMaxCharCount(s, queries):
    # queries is a n x 2 array where queries[i][0] and queries[i][1] represents x[i] and y[i] for the ith query.
    maxCount = []
    finalWord = s.lower()
    for interval in queries:
        if interval[0] == interval[1]:
            maxCount.append(1)
        else:
            string = finalWord[interval[0]:interval[1]+1]
            maxCount.append(string.count(max(string)))
    return maxCount

Any help would be appreciated

Answer 1

PEP 8

The Style Guide for Python Code’s naming conventions recommends again mixedCase identifiers. CapWords are for classes and types, snake_case is for functions, methods and variables. Thus, getMaxCharCount, maxCount and finalWord should be renamed to get_max_char_count, max_count and final_word.

string

string is an importable module in Python. Its use as an identifier should be discouraged.

Intervals

interval is a perfectly fine variable, but interval[0] and interval[1] are confusing. Are those the zeroth and first intervals in a list of intervals? It would be better to unpack the interval immediately into the starting and ending values of the interval. This can even be done directly by the for statement:

    for start, end in queries:
        if start == end:
            ...

Special Casing

You have special-cased the length 1 interval. Why? Does the general purpose version of the code not work for the length one interval? Is it too slow? Is the special-case a common occurrence, or does checking for it actually slow down the general purpose case be introducing an unnecessary if statement?

List Comprehension

If we remove the special-case, your code reads approximately:

    max_count = []
    for start, end in queries:
        max_count.append(...)

This pattern is usually re-written using list-comprehension, since it is much faster than repeated calls to .append():

    max_count = [ ... for start, end in queries ]

The only issue is what should be used in place of .... Prior to Python 3.7, there was no easy way to refer to the result of a computation multiple times in one expression. Python 3.8 introduces the “walrus operator” (:=) which allows variables to be assigned inside of other expressions. We can use this to avoid referencing and slicing final_word twice:

    max_count = [ (span := final_word[start:end+1]).count(max(span)) for start, end in queries ]

Reworked Code (Python 3.8)

def get_max_char_count(s, queries):
    final_word = s.lower()
    return [(span := final_word[start:end+1]).count(max(span)) for start, end in queries]

This code may be slightly faster than your original code, with the speed up mostly from replacing .append with list comprehension. To really see significant speed gains, you need to improve the algorithm.

Algorithmic Improvement

Since this is a coding challenge, I won’t give you code for the better algorithm, but I will get you started in the right direction.

How many times are you looking at any given character of final_word?

Consider the following test case:

2000
AAAAAAAAAAA...[2000 A’s] ... AAAAAAAAAAAA
2000
0 1999
0 1999
0 1999
  :      :
[2000 duplicate lines]
  :      :
0 1999
0 1999

The result should be a list of 2000 copies of the number 2000. We did this in our head. Your algorithm will test each character 4000 times; 2000 times during max and another 2000 times during count. Clearly, we’ve got room for improvement. The ideal would be if each character was only tested twice, once during max, and once during count. But how can we achieve this?

Consider another test case:

20
AAAABBBBCCCCBBBBCCCC
3
0 11
4 15
8 19

Can you see any way of computing intermediate results and reusing them?

Can you divide this into 5 subproblems? Can you combine the first 3 subproblems together to get the first answer? 4 A’s, 4 B’s and 4 C’s makes 4 C’s. Subproblems 2 to 4 to get the second answer? 4 B’s, 4 C’s and 4 B’s makes 4 C’s. Subproblems 3 to 5 to get the 3rd answer? 4 C’s, 4 B’s and 4 C’s makes 8 C’s. How would you store the subproblems results? Where did we get the boundaries of the subproblems?