1079.letter-tile-possibilities.cpp

/*
 * @lc app=leetcode id=1079 lang=cpp
 *
 * [1079] Letter Tile Possibilities
 */

// @lc code=start
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)
// @lc code=end