Как получить число всех уникальных перестановок длины k из строки длины n?

Question

Предположим, нам даны строки s = "aba" и k = 2. Тогда перестановки, которые мы можем сделать, используя строковые символы, равны

aa ab ba

Итак, ответ 3.

Если s = "aabb" и k = 2, то возможные перестановки равны

aa ab ba bb 

Итак, ответ 4.

Мы можем использовать символ только столько раз, сколько он появляется в строке или меньше, но не более того.

Есть ли какая-нибудь формула или какой-нибудь способ быстро ее выяснить?

Примечание: K - это не количество уникальных символов, например. s = "aabbcdd" значение k может составлять k = 3.

Answer 1

import java.util.*;

class solution {
 static int findPermutation(String str, int k) {
  boolean[] has = new boolean[26];
  Arrays.fill(has, false);
  int cnt = 0;

  for (int i = 0; i < str.length(); i++) {
   if (!has[str.charAt(i) - 'a']) {

    cnt++;

    has[str.charAt(i) - 'a'] = true;
   }
  }

  int ans = 1;

  for (int i = 2; i <= cnt; i++)
   ans *= i;

  for (int i = cnt - k; i > 1; i--)
   ans /= i;
  return ans;
 }

 // Driver code 
 public static void main(String args[]) {
  String str = "rrpk";
  int k = 2;
  System.out.println(findPermutation(str, k));

 }
}

ALGO: сначала подсчитайте уникальные символы в строке, затем возьмите k символов из списка уникальных символов и расположите их, т.е. nPr = n! / (n - r)!.