find-original-i.py (1199B)
1 # idea: 2 3 # get the counts of each character 4 # the total number of possible strings is 5 # the number of 2 selections of characters that result in a 6 # different word. 7 8 # the counting approach likely won't work because it doesn't 9 # handle duplicate strings correctly, as is the case with 'aaa' 10 # which can only become 'a' or 'aa' but not 'aa' and 'aa'. 11 12 # recursive approach: 13 # given the word we create a count branch 14 # every time the current character is the same as the previous 15 # at each branch we continue on assuming it is either their or not 16 # how do we handle duplicates then? 17 # to handle duplicate we could memoize but that's slow 18 # we could also skip any character that is a run 19 # and then evaluate all unique selections of it at the end 20 # this runs in linear time and should be simple to do 21 22 23 class Solution: 24 25 def possibleStringCount(self, word: str) -> int: 26 return recurse(word, 0) 27 28 29 def recurse(word, idx) -> int: 30 31 if idx == len(word): 32 return 1 33 34 duplicates = 1 35 36 while idx < len(word) - 1 and word[idx] == word[idx + 1]: 37 duplicates += 1 38 idx += 1 39 40 word_count = duplicates - 1 41 42 word_count += recurse(word, idx + 1) 43 44 return word_count