Letter tile possibilities

Hash Table String Backtracking Counting

83.5% acceptance

Feb 25, 2026

3137

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn num_tile_possibilities(tiles: String) -> i32 {
    let mut freq = [0i32; 26];
    for b in tiles.bytes() { freq[(b - b'A') as usize] += 1; }
    fn dfs(freq: &mut [i32; 26]) -> i32 {
      let mut res = 0;
      for i in 0..26 {
        if freq[i] > 0 {
          res += 1;
          freq[i] -= 1;
          res += dfs(freq);
          freq[i] += 1;
        }
      }
      res
    }
    dfs(&mut freq)
  }
}