Today I have done leetcode's February LeetCoding Challenge with cpp.

February LeetCoding Challenge 17

Description

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 {
  int permutation[8] = {1, 1, 2, 6, 24, 120, 720, 5040};
  int answer = 0;
  map<char, int> mp;
  
  int result(vector<int> &chars, int len) {
    int res = permutation[len];
    for(auto cnt : chars) res /= permutation[cnt];
    return res;
  }
  
  void helper(map<char, int>::iterator &it, vector<int> chars, int len, int count) {
    if(it == mp.end()) {
      if(count == len) answer += result(chars, len);
      return;
    }
    
    for(int i = 0; i <= it->second; ++i) {
      chars.push_back(i);
      ++it;
      helper(it, chars, len, count + i);
      --it;
      chars.pop_back();
    }
  }
public:
  int numTilePossibilities(string tiles) {
    for(auto c : tiles) mp[c] += 1;
    vector<int> tmp;
    auto tmpIt = mp.begin();
    for(int i = 1; i <= tiles.length(); ++i) {
      helper(tmpIt, tmp, i, 0);
    }
    return answer;
  }
};

// Accepted
// 86/86 cases passed (0 ms)
// Your runtime beats 100 % of cpp submissions
// Your memory usage beats 53.21 % of cpp submissions (10.7 MB)