Algorithm
Problem Name: 1079. Letter Tile Possibilities
Problem Link: https://leetcode.com/problems/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 <= 7tilesconsists of uppercase English letters.
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int numTilePossibilities(String tiles) {
int[] count = new int[26];
for (char c : tiles.toCharArray()) {
count[c - 'A']++;
}
return dfs(count);
}
private int dfs(int[] count) {
int sum = 0;
for (int i = 0; i < 26; i++) {
if (count[i] == 0) {
continue;
}
sum++;
count[i]--;
sum += dfs(count);
count[i]++;
}
return sum;
}
}
Input
tiles = "AAB"
Output
8
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const numTilePossibilities = function(tiles) {
const obj = { count: 0 };
dfs(tiles, new Array(tiles.length).fill(false), new Set(), "", obj);
return obj.count;
};
function dfs(tiles, used, visited, path, obj) {
if (path !== "" && !visited.has(path)) obj.count++;
visited.add(path)
for (let i = 0; i < tiles.length; i++) {
if (used[i]) continue;
used[i] = true;
dfs(tiles, used, visited, path + tiles.charAt(i), obj);
used[i] = false;
}
}
Input
tiles = "AAB"
Output
8
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def numTilePossibilities(self, tiles: str) -> int:
return sum(len(set(itertools.permutations(tiles, i))) for i in range(1, len(tiles) + 1))
Input
tiles = "V"
Output
1
#4 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _1079_LetterTilePossibilities
{
public int NumTilePossibilities(string tiles)
{
var counts = new int[26];
foreach (var ch in tiles)
counts[ch - 'A']++;
return DFS(counts);
}
private int DFS(int[] counts)
{
var sum = 0;
for (int i = 0; i < 26; i++)
{
if (counts[i] == 0) continue;
sum++;
counts[i]--;
sum += DFS(counts);
counts[i]++;
}
return sum;
}
}
}
Input
tiles = "V"
Output
1