Question 1: Consider a string to be valid if the first letter is A, and each subsequent letter is
either a letter that has already appeared somewhere in the string, or the next letter in the
alphabet. So if you’ve had As and Bs so far, A, B, or C would be a valid next letter, but D would
not because you haven’t had a C yet. Describe in words how you would write a function that
takes in a string and determines if it’s valid.
Using the same definition of “valid”, write a function that takes in an integer N and
prints all the valid strings of length N. Don’t worry about the case where n is greater than 26;
you can assume that will never happen.
eg.,
N = 3
AAA, AAB, ABA, ABB, ABC
AAC
my solution:
def get_all_valid_combinations(N: int) -> 'List[str]':
""" """
if not (0 < N < 27):
raise ValueError()
def helper(current: List['str'], seen: set, maxi: chr):
"""goes on building string using backtracking """
if len(current) == N:
print(''.join(current))
return
for char in seen | {chr(ord(maxi) + 1)}:
helper(current + [char], seen | {char}, max(maxi, char))
base = ['a']
seen = set('a')
maxi = 'a'
helper(base, seen, maxi)
N = 4
get_all_valid_combinations(N)# for N = 3, the output will be abb
aaa
aab
aba
abc
abb
For my solution the time complexity seems: O(N^N) and space : O(N)
as for each next call to the function there available charaters are current length of string + 1 ie N+1 1*2 + 2*3 + 3 *4.... = N^N
OPTIMIZED Solution
def get_all_valid_combinations(N: int) -> 'List[str]':
""" """
if not (0 < N < 27):
raise ValueError()
def helper(current: str):
"""goes on building string using backtracking """
nonlocal uniq_count
if len(current) == N:
print(''.join(current))
return
# use already existing charts
for i in range(uniq_count):
current.append(chr(ord('a') + i))
helper(current)
current.pop()
# time for new charater
current.append(chr(ord('a') + uniq_count))
uniq_count += 1
helper(current)
current.pop()
uniq_count -= 1
base = ['a']
uniq_count = 1 # count of unique characters as current will be only in growing order ie a, b,..
helper(base)
N = 4
get_all_valid_combinations(N)