In this guide, you will get 1079. Letter Tile Possibilities LeetCode Solution with the best time and space complexity. The solution to Letter Tile Possibilities problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
Complexity Analysis
Time Complexity: O(n^{26})
Space Complexity: O(n)
1079. Letter Tile Possibilities LeetCode Solution in C++
class Solution {
public:
int numTilePossibilities(string tiles) {
vector<int> count(26);
for (const char t : tiles)
++count[t - 'A'];
return dfs(count);
}
private:
int dfs(vector<int>& count) {
int possibleSequences = 0;
for (int& c : count) {
if (c == 0)
continue;
// Put c in the current position. We only care about the number of
// possible sequences of letters but don't care about the actual
// combination.
--c;
possibleSequences += 1 + dfs(count);
++c;
}
return possibleSequences;
}
}; /* code provided by PROGIEZ */
1079. Letter Tile Possibilities LeetCode Solution in Java
class Solution {
public int numTilePossibilities(String tiles) {
int[] count = new int[26];
for (final char t : tiles.toCharArray())
++count[t - 'A'];
return dfs(count);
}
private int dfs(int[] count) {
int possibleSequences = 0;
for (int i = 0; i < 26; ++i) {
if (count[i] == 0)
continue;
// Put c in the current position. We only care about the number of possible
// sequences of letters but don't care about the actual combination.
--count[i];
possibleSequences += 1 + dfs(count);
++count[i];
}
return possibleSequences;
}
} // code provided by PROGIEZ
1079. Letter Tile Possibilities LeetCode Solution in Python
class Solution:
def numTilePossibilities(self, tiles: str) -> int:
count = collections.Counter(tiles)
def dfs(count: dict[int, int]) -> int:
possibleSequences = 0
for k, v in count.items():
if v == 0:
continue
# Put c in the current position. We only care about the number of possible
# sequences of letters but don't care about the actual combination.
count[k] -= 1
possibleSequences += 1 + dfs(count)
count[k] += 1
return possibleSequences
return dfs(count) # code by PROGIEZ
