一意のサブシーケンスを数える

入力として文字列を指定すると、その中の各文字の各サブシーケンスの出現が同じになるようなサブシーケンスの数を返します。

例：

input string = baab
Result = 11

説明：

length 1 subsequences = [b, a, a, b] => each letter occurs only once
length 2 subsequences = [ba, ba, ab, ab, bb, aa] => in ab , a and b occurs same number of times
length of 3 = []
length of 4 = [baab] => here a occurs twice also b occurs twice
So we have 11 combinations

ブルートフォースアプローチを使用した私のコードは次のとおりです。

import java.util.*;

public class Main {
    static List<String> list = new ArrayList<>();

    public static void main(String[] args) {
        String s = "baab";
        findsubsequences(s, "");
        // sort the strings by length
        list.sort((a,b) -> a.length() - b.length());
        long result = 0;
        // verify and count valid subsequences.
        for(String e : list) {
            e = e.trim();
            if(e.length() == 0) continue;
            int max = 0;
            Map<Character, Integer> map = new HashMap<>();
            for(char c : e.toCharArray()) {
                map.put(c, map.getOrDefault(c,0)+1);
                max = Math.max(max, map.get(c));
            }
            boolean valid = true;
            for(char c : map.keySet()) {
                if(map.get(c) != max) {
                    valid = false;
                    break;
                }
            }
            if(valid) {
                result++;
            }
        }
        System.out.println("Answer is : " + result);
    }

    // Method to get list of subsequences
    private static void findsubsequences(String s,String ans) {
        if (s.length() == 0) {
            list.add(ans);
            return;
        }
        // We add adding 1st character in string
        findsubsequences(s.substring(1), ans + s.charAt(0));
        findsubsequences(s.substring(1), ans);
    }
}

問題

string contains only lowercase english alphabets
length of input string is 1 to 10^5

私のコードにはO(2^n)の時間がかかります。これをより少ない時間で解決する正しい方法は何ですか。