Arrange II

• Time : $O(size(A) * B)$
• Space : $O(size(A) * B)$

long long helper(vector<vector<long long>>& dp, string s, int p, int k) {
    if(p == s.length()) return k <= 0 ? 0 : INT_MAX;
    if(k <= 0) return INT_MAX;
    if(k == s.length() - p) return 0;
    if(dp[p][k] != -1) return dp[p][k];
    long long& res = dp[p][k] = INT_MAX;
    long long w = 0, b = 0;
    for(int i = p; i <= s.length() - k; i++) {
        if(s[i] == 'W') w++;
        else b++;
        res = min(res, w * b + helper(dp,s,i+1,k-1));
    }
    return res;
}

int Solution::arrange(string A, int B) {
    int n = A.length();
    if(n < B) return -1;
    if(n == B) return 0;
    vector<vector<long long>> dp(n, vector<long long>(B + 1, -1));
    return helper(dp,A,0,B);
}