# Leetcode Contest 140

#### Letter Tile Possibilities

You have a set of tiles, where each tile has one letter tiles[i] printed on it. Return the number of possible non-empty sequences of letters you can make.

Keyword: permutation

• Sort not needed
• Use a helper method to iterate over all possibilities, use set to avoid repetition

Similar to: 47. Permutations II

``````class Solution(object):
def numTilePossibilities(self, tiles):
"""
:type tiles: str
:rtype: int
"""
record = set()

def helper(currString, remainingCharacters):
if len(remainingCharacters) == 0:
return
if currString in record:
return
for i in range(len(remainingCharacters)):
helper(currString + remainingCharacters[i], remainingCharacters[:i] + remainingCharacters[i+1:])

helper("", tiles)
print record, len(record)
return len(record) - 1``````

Another one line brute force solution from discuss:

``````    def numTilePossibilities(self, S):
return len({s[:i] for s in itertools.permutations(S) for i in xrange(8)})``````

#### Insufficient Nodes in Root to Leaf Paths

Given the root of a binary tree, consider all root to leaf paths: paths from the root to any leaf. (A leaf is a node with no children.) A node is insufficient if every such root to leaf path intersecting this node has sum strictly less than limit. Delete all insufficient nodes simultaneously, and return the root of the resulting binary tree.

Keyword: Tree, DFS, recursive

• I didn’t pass this question due to one very long test case failure.
• However the solution won’t be too different, so I consider it solved 😂

Recursive solution:

``````class Solution(object):
def sufficientSubset(self, root, limit):
"""
:type root: TreeNode
:type limit: int
:rtype: TreeNode
"""
if root == None: return None
if root.left == None and root.right == None:
return root if root.val >= limit else None
if root.left != None:
root.left = self.sufficientSubset(root.left, limit - root.val)
if root.right != None:
root.right = self.sufficientSubset(root.right, limit - root.val)
return root``````

#### Smallest Subsequence of Distinct Characters

Return the lexicographically smallest subsequence of text that contains all the distinct characters of text exactly once.

Keyword: Greedy

• Same as Remove Duplicate Letters
• Idea: when met a new character `c`, if the last item in our current result is larger than `c`, and the last item still remains later, then we remove it for now.
• A very nice solution explained: link
``````class Solution(object):
def smallestSubsequence(self, text):
"""
:type text: str
:rtype: str
"""
record = {}
for index, c in enumerate(text):
record[c] = index
print record

result = []
for index, c in enumerate(text):
if c in result:
continue
while len(result) > 0 and result[-1] > c and record[result[-1]] > index:
# if the last character is larger than c, and the character still remains in text, remove it
result.pop()
result.append(c)
return ''.join(result)``````