Solution to Cassidoo's Long Substrings Problem

Here is my initial solution, which uses nested loops to check for substring candidates, while using a couple of clever shortcuts to skip substrings that are known to be too long. As before, it is written in python 3.9.2 (hence the snake_case).

#!/usr/bin/env python3

# preconditions:
# - text_body is a valid non-None python string.
# - distinct_letter_cap (k) is some positive integer (2 in this week's problem)
# postcondition:
# - computes the length of the longest substring with no more than k distinct
# letters.
def multi_param_substring(text_body, distinct_letter_cap):

text_length = len(text_body)
# it's gotta be at least two characters long! ;)
current_longest_length = distinct_letter_cap
if (text_length < current_longest_length):

return text_length

for start_ind in range(0, text_length-distinct_letter_cap):

if (start_ind+current_longest_length > text_length):

# if the current longest length already puts us out-of-bounds, then
# we'll never find any substring long enough!
return current_longest_length

# now that that edge case is taken care of, get the end_ind,
# which must be a valid "final index".
end_ind = start_ind+current_longest_length
keep_growing = True

while (keep_growing):

keep_checking = True
distinct_letters = {}
for check_ind in range(start_ind, end_ind):

# update the distinct_letters dict
if (text_body[check_ind] in distinct_letters.keys()):

distinct_letters[text_body[check_ind]] += 1

else:

distinct_letters[text_body[check_ind]] = 1

# ... and check the new size.
if (distinct_letter_cap < len(distinct_letters.keys())):

keep_checking = False
break

if (keep_checking):

# the candidate is valid, keep trying to expand it!
# Here I decide to expand strings "to the right;"
# but it should not matter as long as one is consistent
# when ruling out invalid substrings.

        current_longest_length = end_ind - start_ind if end_ind-start_ind > current_longest_length else current_longest_length

if (end_ind == text_length):

keep_growing = False

else:

end_ind += 1

else:

# candidate already has too many distinct letters;
# do not bother expanding further (to the right).
# just give up and increment start_ind.
keep_growing = False

return current_longest_length

def unique_substr(str_text):

return multi_param_substring(str_text, 2)

if (__name__ == "__main__"):

print("cassidoo problem (from 2024-04-15)")
s = input("Enter the string in question: ")
result = unique_substr(s)
print(f"{result}")

2024-04-15 | Cassidoo's uniqueSubstr Problem