Welcome to Subscribe On Youtube

1079. Letter Tile Possibilities

Description

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.

Solutions

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      public int numTilePossibilities(String tiles) {
          int[] cnt = new int[26];
          for (char c : tiles.toCharArray()) {
              ++cnt[c - 'A'];
          }
          return dfs(cnt);
      }
  
      private int dfs(int[] cnt) {
          int res = 0;
          for (int i = 0; i < cnt.length; ++i) {
              if (cnt[i] > 0) {
                  ++res;
                  --cnt[i];
                  res += dfs(cnt);
                  ++cnt[i];
              }
          }
          return res;
      }
  }
  

• class Solution {
  public:
      int numTilePossibilities(string tiles) {
          int cnt[26]{};
          for (char c : tiles) {
              ++cnt[c - 'A'];
          }
          function<int(int* cnt)> dfs = [&](int* cnt) -> int {
              int res = 0;
              for (int i = 0; i < 26; ++i) {
                  if (cnt[i] > 0) {
                      ++res;
                      --cnt[i];
                      res += dfs(cnt);
                      ++cnt[i];
                  }
              }
              return res;
          };
          return dfs(cnt);
      }
  };
  

• class Solution:
      def numTilePossibilities(self, tiles: str) -> int:
          def dfs(cnt: Counter) -> int:
              ans = 0
              for i, x in cnt.items():
                  if x > 0:
                      ans += 1
                      cnt[i] -= 1
                      ans += dfs(cnt)
                      cnt[i] += 1
              return ans
  
          cnt = Counter(tiles)
          return dfs(cnt)
  
  

• func numTilePossibilities(tiles string) int {
  	cnt := [26]int{}
  	for _, c := range tiles {
  		cnt[c-'A']++
  	}
  	var dfs func(cnt [26]int) int
  	dfs = func(cnt [26]int) (res int) {
  		for i, x := range cnt {
  			if x > 0 {
  				res++
  				cnt[i]--
  				res += dfs(cnt)
  				cnt[i]++
  			}
  		}
  		return
  	}
  	return dfs(cnt)
  }
  

• function numTilePossibilities(tiles: string): number {
      const cnt: number[] = new Array(26).fill(0);
      for (const c of tiles) {
          ++cnt[c.charCodeAt(0) - 'A'.charCodeAt(0)];
      }
      const dfs = (cnt: number[]): number => {
          let res = 0;
          for (let i = 0; i < 26; ++i) {
              if (cnt[i] > 0) {
                  ++res;
                  --cnt[i];
                  res += dfs(cnt);
                  ++cnt[i];
              }
          }
          return res;
      };
      return dfs(cnt);
  }
  
  

All Problems

All Solutions