Counting Non-Empty Subsequences with Repeated Characters

How many non-empty subsequences can you form from a string that has repeated characters?

The shortest subsequence has length 1. The longest has the full length of the string. For each possible length, we go through each position and choose either a specific character A from our string, or we skip to the next non-A character. This avoids counting duplicates.

Here’s how the algorithm works:

class Solution {
    int fact[8] = {1, 1, 2, 6, 24, 120, 720, 5040};
    
    int countPerm(string s) {
        int l = s.size();
        int cnt[26] = {};
        for(auto c : s) ++cnt[c-'A'];
        int fa=1;
        for(int i=0;i<26;++i) {
            fa *= fact[cnt[i]];
        }
        return fact[l]/fa;
    }
    
    void DFS(string& str, string& s, int pos, int i, int &curl, int &l, int &res) {
        if (pos == curl) {
            res += countPerm(s);
            return;
        }
        
        if (i>=l) return;
        
        s.push_back(str[i]);
        DFS(str, s, pos+1, i+1, curl, l, res);
        while(i<l-1 && str[i]==str[i+1]) ++i;
        s.pop_back();
        DFS(str, s, pos, i+1, curl, l, res);
    }
    
public:
    int numTilePossibilities(string tiles) {
        int res = 0;
        int len = tiles.size();
        sort(tiles.begin(), tiles.end());
        
        for(int i=1;i<=len;++i) {
            string tmp;
            DFS(tiles, tmp, 0, 0, i, len, res);
        }
        
        return res;
    }
};

The code sorts the input first. Then for each target length from 1 to the full string length, it builds subsequences using depth-first search. When we encounter repeated characters, we skip over them to avoid generating duplicate subsequences.

This approach handles the repetition problem directly in the search process rather than generating all possibilities and filtering out duplicates later.

#backtracking #enumeration

Counting Bits Fast Counting Trailing Zeros in Factorials