K length words that can be formed from given characters without repetition

Namachila November 18, 2025

0 0 5 minutes read

Given an integer k and a string str consisting of lowercase English alphabets, the task is to count how many k-character words (with or without meaning) can be formed from the characters of str when repetition is not allowed.

Examples:

Input: str = “cat”, k = 3
Output: 6
Required words are “cat”, “cta”, “act”, “atc”, “tca” and “tac”.

Input: str = “zambiatek”, k = 3
Output: 840

Approach: Count the number of distinct characters in str and store it in cnt, now the task is to arrange k characters out of cnt characters i.e. ⁿP_r = n! / (n – r)!.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the required count
int findPermutation(string str, int k)
{
    bool has[26] = { false };
 
    // To store the count of distinct characters in str
    int cnt = 0;
 
    // Traverse str character by character
    for (int i = 0; i < str.length(); i++) {
 
        // If current character is appearing
        // for the first time in str
        if (!has[str[i] - 'a']) {
 
            // Increment the distinct character count
            cnt++;
 
            // Update the appearance of the current character
            has[str[i] - 'a'] = true;
        }
    }
 
    long long int ans = 1;
 
    // Since P(n, r) = n! / (n - r)!
    for (int i = 2; i <= cnt; i++)
        ans *= i;
 
    for (int i = cnt - k; i > 1; i--)
        ans /= i;
 
    // Return the answer
    return ans;
}
 
// Driver code
int main()
{
    string str = "zambiatek";
    int k = 4;
    cout << findPermutation(str, k);
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class solution
{
// Function to return the required count
static int findPermutation(String str, int k)
{
    boolean[] has = new boolean[26];
    Arrays.fill(has,false);
 
    // To store the count of distinct characters in str
    int cnt = 0;
 
    // Traverse str character by character
    for (int i = 0; i < str.length(); i++) {
 
        // If current character is appearing
        // for the first time in str
        if (!has[str.charAt(i) - 'a']) 
        {
 
            // Increment the distinct character count
            cnt++;
 
            // Update the appearance of the current character
            has[str.charAt(i) - 'a'] = true;
        }
    }
 
    int ans = 1;
 
    // Since P(n, r) = n! / (n - r)!
    for (int i = 2; i <= cnt; i++)
        ans *= i;
 
    for (int i = cnt - k; i > 1; i--)
        ans /= i;
 
    // Return the answer
    return ans;
}
 
// Driver code
public static void main(String args[])
{
    String str = "zambiatek";
    int k = 4;
    System.out.println(findPermutation(str, k));
 
}
}
// This code is contributed by
// Sanjit_prasad

Python3

# Python3 implementation of the approach
import math as mt 
 
# Function to return the required count
def findPermutation(string, k):
 
    has = [False for i in range(26)]
 
    # To store the count of distinct 
    # characters in str
    cnt = 0
 
    # Traverse str character by character
    for i in range(len(string)):
         
        # If current character is appearing
        # for the first time in str
        if (has[ord(string[i]) - ord('a')] == False):
 
            # Increment the distinct
            # character count
            cnt += 1
 
            # Update the appearance of the 
            # current character
            has[ord(string[i]) - ord('a')] = True
         
    ans = 1
 
    # Since P(n, r) = n! / (n - r)!
    for i in range(2, cnt + 1):
        ans *= i
 
    for i in range(cnt - k, 1, -1):
        ans //= i
 
    # Return the answer
    return ans
 
# Driver code
string = "zambiatek"
k = 4
print(findPermutation(string, k))
 
# This code is contributed 
# by Mohit kumar 29

C#

// C# implementation of the approach 
 
using System;
 
class solution 
{ 
// Function to return the required count 
static int findPermutation(string str, int k) 
{ 
    bool []has = new bool[26]; 
     
    for (int i = 0; i < 26 ; i++) 
        has[i] = false;
 
    // To store the count of distinct characters in str 
    int cnt = 0; 
 
    // Traverse str character by character 
    for (int i = 0; i < str.Length; i++) { 
 
        // If current character is appearing 
        // for the first time in str 
        if (!has[str[i] - 'a']) 
        { 
 
            // Increment the distinct character count 
            cnt++; 
 
            // Update the appearance of the current character 
            has[str[i] - 'a'] = true; 
        } 
    } 
 
    int ans = 1; 
 
    // Since P(n, r) = n! / (n - r)! 
    for (int i = 2; i <= cnt; i++) 
        ans *= i; 
 
    for (int i = cnt - k; i > 1; i--) 
        ans /= i; 
 
    // Return the answer 
    return ans; 
} 
 
// Driver code 
public static void Main() 
{ 
    string str = "zambiatek"; 
    int k = 4; 
    Console.WriteLine(findPermutation(str, k)); 
 
} 
// This code is contributed by Ryuga
} 

PHP

<?php
// PHP implementation of the approach
 
// Function to return the required count
function findPermutation($str, $k)
{
    $has = array();
     
    for ($i = 0; $i < 26; $i++)
    {
        $has[$i]= false;
    }
     
    // To store the count of distinct characters in $str
    $cnt = 0;
 
    // Traverse $str character by character
    for ($i = 0; $i < strlen($str); $i++)
    {
 
        // If current character is appearing
        // for the first time in $str
        if ($has[ord($str[$i]) - ord('a')] == false) 
        {
 
            // Increment the distinct character count
            $cnt++;
 
            // Update the appearance of the current character
            $has[ord($str[$i]) - ord('a')] = true;
        }
    }
 
    $ans = 1;
 
    // Since P(n, r) = n! / (n - r)!
    for ($i = 2; $i <= $cnt; $i++)
        $ans *= $i;
 
    for ($i = $cnt - $k; $i > 1; $i--)
        $ans /= $i;
 
    // Return the answer
    return $ans;
}
 
// Driver code
$str = "zambiatek";
$k = 4;
echo findPermutation($str, $k);
 
 
// This code is contributed by ihritik
?>

Javascript

<script>
      // JavaScript implementation of the approach
      // Function to return the required count
      function findPermutation(str, k) {
        var has = new Array(26);
 
        for (var i = 0; i < 26; i++) has[i] = false;
 
        // To store the count of distinct characters in str
        var cnt = 0;
 
        // Traverse str character by character
        for (var i = 0; i < str.length; i++) {
          // If current character is appearing
          // for the first time in str
 
          if (!has[str[i].charCodeAt(0) - "a".charCodeAt(0)]) {
            // Increment the distinct character count
            cnt++;
 
            // Update the appearance of the current character
            has[str[i].charCodeAt(0) - "a".charCodeAt(0)] = true;
          }
        }
 
        var ans = 1;
 
        // Since P(n, r) = n! / (n - r)!
        for (var i = 2; i <= cnt; i++) ans *= i;
 
        for (var i = cnt - k; i > 1; i--) ans /= i;
 
        // Return the answer
        return ans;
      }
 
      // Driver code
      var str = "zambiatek";
      var k = 4;
      document.write(findPermutation(str, k));
    </script>

Output

Time Complexity: O(n), where n is the length of the given string.
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!