<jupyter_start><jupyter_text>Find longest word in dictionary that subsequence of given stringcode-challengehttps://techdevguide.withgoogle.com/paths/foundational/find-longest-word-in-dictionary-that-subsequence-of-given-stringcode-challengeThe ChallengeGiven a string S and a set of words D, find the longest word in D that is a subsequence of S.Word W is a subsequence of S if some number of characters, possibly zero, can be deleted from S to form W, without reordering the remaining characters.Note: D can appear in any format (list, hash table, prefix tree, etc.For example, given the input of S = "abppplee" and D = {"able", "ale", "apple", "bale", "kangaroo"} the correct output would be "apple"* The words "able" and "ale" are both subsequences of S, but they are shorter than "apple".* The word "bale" is not a subsequence of S because even though S has all the right letters, they are not in the right order.* The word "kangaroo" is the longest word in D, but it isn't a subsequence of S.<jupyter_code>S = "abppplee"

# Sorting the set based on length of the words
D = {"able", "ale", "apple", "bale", "kangaroo", "abppple"}
D = sorted(D, key=len, reverse=True)
print(D)

# Check each word in D to see if it is a possible sequence...
for word in D:
    word_index = 0
    string_index = 0
    while word_index < len(word) and string_index < len(S):
        if word[word_index] == S[string_index]:
            word_index += 1
            string_index += 1
        else:
            string_index += 1
    
    if word_index == len(word) and string_index <= len(S):
        print(word)
        break<jupyter_output>['kangaroo', 'abppple', 'apple', 'able', 'bale', 'ale']
abppple<jupyter_text>```!/usr/bin/env pythonimport collectionsimport sysdef find_longest_word_in_string(letters, words):    letter_positions = collections.defaultdict(list)     For each letter in 'letters', collect all the indices at which it appears.     O(letters) space and speed.    for index, letter in enumerate(letters):        letter_positions[letter].append(index)     For words, in descending order by length...     Bails out early on first matched word, and within word on     impossible letter/position combinations, but worst case is     O(words  avg-len) * O(letters / 26) time; constant space.     With some work, could be O(W * avg-len) * log2(letters/26)     But since binary search has more overhead     than simple iteration, log2(letters) is about as      expensive as simple iterations as long as      the length of the arrays for each letter is     “small”.  If letters are randomly present in the     search string, the log2 is about equal in speed to simple traversal     up to lengths of a few hundred characters.                  for word in sorted(words, key=lambda w: len(w), reverse=True):        pos = 0        for letter in word:            if letter not in letter_positions:                break         Find any remaining valid positions in search string where this         letter appears.  It would be better to do this with binary search,         but this is very Python-ic.        possible_positions = [p for p in letter_positions[letter] if p >= pos]        if not possible_positions:            break        pos = possible_positions[0] + 1        else:             We didn't break out of the loop, so all letters have valid positions              return wordif __name__ == '__main__':    print subdict(sys.argv[1], sys.argv[2:])```  string_splosionGiven a non-empty string like "Code" return a string like "CCoCodCode".string_splosion('Code') → 'CCoCodCode'string_splosion('abc') → 'aababc'string_splosion('ab') → 'aab'<jupyter_code>def string_splosion(str):
  output = ""
  for i in range(len(str)):
    output += str[:i+1]
  return output

print("string_splosion('Code') → 'CCoCodCode'")    
print(f"output: {string_splosion('Code')}")

print("string_splosion('abc')  → 'aababc'")    
print(f"output: {string_splosion('abc')}")

print("string_splosion('ab')  → 'aab'")    
print(f"output: {string_splosion('ab')}")<jupyter_output>string_splosion('Code') → 'CCoCodCode'
output: CCoCodCode
string_splosion('abc')  → 'aababc'
output: aababc
string_splosion('ab')  → 'aab'
output: aab<jupyter_text>maxSpanConsider the leftmost and righmost appearances of some value in an array. We'll say that the "span" is the number of elements between the two inclusive. A single value has a span of 1. Returns the largest span found in the given array. (Efficiency is not a priority.)maxSpan([1, 2, 1, 1, 3]) → 4maxSpan([1, 4, 2, 1, 4, 1, 4]) → 6maxSpan([1, 4, 2, 1, 4, 4, 4]) → 6<jupyter_code>import collections

def maxSpan(input):
    number_positions = collections.defaultdict(list)
    
    for index, number in enumerate(input):
        number_positions[number].append(index)
    
    output = 0
    for number in number_positions:
        current_list = number_positions[number]
        if len(current_list) > 1:
            current_span = current_list[-1] - current_list[0] + 1
        else:
            current_span = 1
        
        if current_span > output:
            output = current_span

    return output

print("maxSpan([1, 2, 1, 1, 3]) → 4")    
print(f"output: {maxSpan([1, 2, 1, 1, 3])}")

print("maxSpan([1, 4, 2, 1, 4, 1, 4]) → 6")
print(f"output: {maxSpan([1, 4, 2, 1, 4, 1, 4])}")

print("maxSpan([1, 4, 2, 1, 4, 4, 4]) → 6")
print(f"output: {maxSpan([1, 4, 2, 1, 4, 4, 4])}")<jupyter_output>maxSpan([1, 2, 1, 1, 3]) → 4
output: 4
maxSpan([1, 4, 2, 1, 4, 1, 4]) → 6
output: 6
maxSpan([1, 4, 2, 1, 4, 4, 4]) → 6
output: 6<jupyter_text>withoutStringGiven two strings, base and remove, return a version of the base string where all instances of the remove string have been removed (not case sensitive). You may assume that the remove string is length 1 or more. Remove only non-overlapping instances, so with "xxx" removing "xx" leaves "x".withoutString("Hello there", "llo") → "He there"withoutString("Hello there", "e") → "Hllo thr"withoutString("Hello there", "x") → "Hello there"<jupyter_code>def withoutString(base, remove):
    output = ""
    
    base_case_removed = base.lower()
    remove_case_removed = remove.lower()
    
    i = 0
    while i < len(base_case_removed):
        if base_case_removed[i] != remove_case_removed[0]:
            output += base[i]
            i += 1
        else:
            for j in range(len(remove_case_removed)):
                if base_case_removed[i+j] != remove_case_removed[j]:
                    output += base[i]
                    i += 1
                    break
            
            # If all the characters matched, dont append them to output
            if j == len(remove_case_removed)-1:
                i = i+j+1
     
    return output
                    
print('withoutString("Hello there", "llo") → "He there"')
print(f'output: {withoutString("Hello there", "llo")}')

print('withoutString("Hello there", "e") → "Hllo thr"')
print(f'output: {withoutString("Hello there", "e")}')

print('withoutString("Hello there", "x") → "Hello there"')
print(f'output: {withoutString("Hello there", "x")}')<jupyter_output>withoutString("Hello there", "llo") → "He there"
output: He there
withoutString("Hello there", "e") → "Hllo thr"
output: Hllo thr
withoutString("Hello there", "x") → "Hello there"
output: Hello there<jupyter_text>sumNumbers Given a string, return the sum of the numbers appearing in the string, ignoring all other characters. A number is a series of 1 or more digit chars in a row. (Note: Character.isDigit(char) tests if a char is one of the chars '0', '1', .. '9'. Integer.parseInt(string) converts a string to an int.)sumNumbers("abc123xyz") → 123sumNumbers("aa11b33") → 44sumNumbers("7 11") → 18<jupyter_code>numerical_character = [str(i) for i in range(0, 10)]

def sumNumbers(input_str):
    
    start_index = None
    sum = 0
    for index, value in enumerate(input_str):
        
        # if start_index:
        if start_index is not None:
            if value not in numerical_character:
                sum += int(input_str[start_index: index])
                start_index = None
                
            elif index == len(input_str)-1:
                sum += int(input_str[start_index:])
                start_index = None
        
        elif value in numerical_character:
            start_index = index
    
    return sum

print('sumNumbers("abc123xyz") → 123')
print(f'output: {sumNumbers("abc123xyz")}' )

print('sumNumbers("aa11b33") → 44')
print(f'output: {sumNumbers("aa11b33")}')

print('sumNumbers("7 11") → 18')
print(f'output: {sumNumbers("7 11")}')<jupyter_output>sumNumbers("abc123xyz") → 123
output: 123
sumNumbers("aa11b33") → 44
output: 44
sumNumbers("7 11") → 18
output: 18<jupyter_text>canBalanceGiven a non-empty array, return true if there is a place to split the array so that the sum of the numbers on one side is equal to the sum of the numbers on the other side.canBalance([1, 1, 1, 2, 1]) → truecanBalance([2, 1, 1, 2, 1]) → falsecanBalance([10, 10]) → true<jupyter_code>def canBalance(input_list):
    total_sum = 0
    for _ in input_list:
        total_sum += _
    
    forward_sum = 0
    for i in range(len(input_list)):
        forward_sum += input_list[i]
        
        if forward_sum == (total_sum - forward_sum):
            return True
    
    return False


print('canBalance([1, 1, 1, 2, 1]) → true')
print(f'output: {canBalance([1, 1, 1, 2, 1])}')

print('canBalance([2, 1, 1, 2, 1]) → false')
print(f'output: {canBalance([2, 1, 1, 2, 1])}')

print('canBalance([10, 10]) → true')
print(f'output: {canBalance([10, 10])}')<jupyter_output>canBalance([1, 1, 1, 2, 1]) → true
output: True
canBalance([2, 1, 1, 2, 1]) → false
output: False
canBalance([10, 10]) → true
output: True<jupyter_text>Problem of the Day:Given an encoded string, return its decoded string.The encoding rule is: `k[encoded_string]`, where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like `3a or 2[4]`.```Example:                        Input: "3[a]2[bc]"  Output: "aaabcbc"  Input: "2[abc]3[cd]ef"  Output: "abcabccdcdcdef"  Input: "3[a2[c]]"  Output: "accaccacc"```<jupyter_code>def encoded_string(input):
    stack = []
    numbers = [str(i) for i in range(10)]
    
    for ch in input:
        if ch != ']':
            stack.append(ch)
        else:
            # Read non-numerical characters
            substring = []
            popch = None
            
            if len(stack):
                popch = stack.pop()
            
            while popch != '[':
                substring += popch
                if len(stack):
                    popch = stack.pop()
            substring = substring[::-1]
            # print(substring)
            
            # Read numerical characters
            k = []
            popch = None
            
            if len(stack):
                popch = stack.pop()
            
            while popch in numbers:
                k += popch
                if len(stack):
                    popch = stack.pop()
                else:
                    break
            
            # Re-insert the last pop if stack is not empty.
            if len(stack):
                stack.append(popch)
            
            k = int(''.join(k[::-1]))
            # print(k)
            
            tempstr = substring * k
            # print(tempstr)
            
            stack += tempstr
        
    return ''.join(stack)
import unittest

class TestStringMethods(unittest.TestCase):

    def test_case1(self):
        self.assertEqual(encoded_string("3[a]2[bc]"), "aaabcbc")

    def test_case2(self):
        self.assertEqual(encoded_string("2[abc]3[cd]ef"), "abcabccdcdcdef")

    def test_case3(self):
        self.assertEqual(encoded_string("3[a2[c]]"), "accaccacc")
if __name__ == '__main__':
    unittest.main(argv=['first-arg-is-ignored'], exit=False)<jupyter_output>...
----------------------------------------------------------------------
Ran 3 tests in 0.004s

OK
StarcoderdataJupyterStructuredCleanDedup