DEV Community

Abhishek Chaudhary
Abhishek Chaudhary

Posted on

Letter Tile Possibilities

You have n  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 using the letters printed on those tiles.

Example 1:

Input: tiles = "AAB"
Output: 8
Explanation: The possible sequences are "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA".

Example 2:

Input: tiles = "AAABBC"
Output: 188

Example 3:

Input: tiles = "V"
Output: 1

Constraints:

  • 1 <= tiles.length <= 7
  • tiles consists of uppercase English letters.

SOLUTION:

class Solution:
    def numTiles(self, tiles, ctr):
        num = 0
        for c in ctr:
            if ctr[c] > 0:
                num += 1
                num += self.numTiles(tiles + c, {**ctr, c: ctr[c] - 1})
        return num

    def numTilePossibilities(self, tiles: str) -> int:
        n = len(tiles)
        ctr = {}
        for c in tiles:
            ctr[c] = ctr.get(c, 0) + 1
        return self.numTiles("", ctr)
Enter fullscreen mode Exit fullscreen mode

Top comments (0)