CSES Solutions – Creating Strings
Given a string S, your task is to generate all different strings that can be created using its characters.
Examples:
Input: S = “aabac”
Output:
20
aaabc
aaacb
aabac
aabca
aacab
aacba
abaac
abaca
abcaa
acaab
acaba
acbaa
baaac
baaca
bacaa
bcaaa
caaab
caaba
cabaa
cbaaaExplanation: 20 unique strings can be generated by rearranging letters of the string “aabac”.
Input: S = “aba”
Output:
3
aab
aba
baa
Explanation: 3 unique strings can be generated by rearranging letters of the string “aba”.
Approach: To solve the problem, follow the below idea:
The problem can be solved by generating all the possible permutations of the input strings. Since some of these permutations can be same, so we can insert all the permutations to a set. After inserting all the permutations, we can print all the unique strings.
Step-by-step algorithm:
- Generate all the permutations of the input string.
- Insert all the strings to a set to avoid printing duplicate strings.
- Iterate over the set and print all the unique strings.
Below is the implementation of the algorithm:
#include <bits/stdc++.h>
using namespace std;
// function to generate all permutations of string S
set<string> solve(string S)
{
int N = S.length();
sort(S.begin(), S.end());
// set to store all the unique permutations
set<string> uniqueStrings;
do {
uniqueStrings.insert(S);
} while (next_permutation(S.begin(), S.end()));
return uniqueStrings;
}
int main()
{
// Sample Input
string S = "aba";
set<string> uniqueStrings = solve(S);
cout << uniqueStrings.size() << "\n";
for (string str : uniqueStrings) {
cout << str << "\n";
}
}
import java.util.*;
public class Permutations {
// Function to generate all permutations of string S
static Set<String> solve(String S) {
int N = S.length();
char[] charArray = S.toCharArray();
Arrays.sort(charArray);
// Set to store all the unique permutations
Set<String> uniqueStrings = new HashSet<>();
do {
uniqueStrings.add(new String(charArray));
} while (nextPermutation(charArray));
return uniqueStrings;
}
// Function to find the next lexicographically greater permutation
static boolean nextPermutation(char[] array) {
int i = array.length - 2;
while (i >= 0 && array[i] >= array[i + 1]) {
i--;
}
if (i < 0) {
return false; // No next permutation is possible
}
int j = array.length - 1;
while (array[j] <= array[i]) {
j--;
}
// Swap the characters at positions i and j
char temp = array[i];
array[i] = array[j];
array[j] = temp;
// Reverse the suffix after i
reverse(array, i + 1, array.length - 1);
return true;
}
// Function to reverse the characters in the array from start to end
static void reverse(char[] array, int start, int end) {
while (start < end) {
char temp = array[start];
array[start] = array[end];
array[end] = temp;
start++;
end--;
}
}
public static void main(String[] args) {
// Sample Input
String S = "aba";
Set<String> uniqueStrings = solve(S);
System.out.println(uniqueStrings.size());
for (String str : uniqueStrings) {
System.out.println(str);
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
public class PermutationGenerator
{
// Function to generate all permutations of string S
public static HashSet<string> Solve(string S)
{
int N = S.Length;
char[] charArray = S.ToCharArray();
Array.Sort(charArray);
S = new string(charArray);
// set to store all the unique permutations
HashSet<string> uniqueStrings = new HashSet<string>();
do
{
uniqueStrings.Add(S);
} while (NextPermutation(ref S));
return uniqueStrings;
}
// Function to generate the next lexicographically greater permutation
private static bool NextPermutation(ref string S)
{
char[] charArray = S.ToCharArray();
int i = charArray.Length - 2;
while (i >= 0 && charArray[i] >= charArray[i + 1])
{
i--;
}
if (i < 0)
{
return false;
}
int j = charArray.Length - 1;
while (charArray[j] <= charArray[i])
{
j--;
}
char temp = charArray[i];
charArray[i] = charArray[j];
charArray[j] = temp;
Array.Reverse(charArray, i + 1, charArray.Length - i - 1);
S = new string(charArray);
return true;
}
// Main method
public static void Main(string[] args)
{
// Sample Input
string S = "aba";
HashSet<string> uniqueStrings = Solve(S);
Console.WriteLine(uniqueStrings.Count);
foreach (string str in uniqueStrings)
{
Console.WriteLine(str);
}
}
}
// function to generate all permutations of string S
function solve(S) {
const N = S.length;
const sortedS = S.split('').sort().join('');
// Set to store all the unique permutations
const uniqueStrings = new Set();
const generatePermutations = (str, chosen) => {
if (str.length === 0) {
uniqueStrings.add(chosen);
return;
}
for (let i = 0; i < str.length; i++) {
const remaining = str.slice(0, i) + str.slice(i + 1);
generatePermutations(remaining, chosen + str[i]);
}
};
generatePermutations(sortedS, '');
return uniqueStrings;
}
// Sample Input
const S = "aba";
const uniqueStrings = solve(S);
console.log(uniqueStrings.size);
uniqueStrings.forEach(str => {
console.log(str);
});
from itertools import permutations
# Function to generate all permutations of string S
def solve(S):
# Sort the string to ensure unique permutations
S_sorted = sorted(S)
# Use set to store all the unique permutations
unique_strings = set()
# Generate permutations and add them to the set
for perm in permutations(S_sorted):
unique_strings.add(''.join(perm))
return unique_strings
def main():
# Sample Input
S = "aba"
# Call the function to find unique permutations
unique_strings = solve(S)
# Print the number of unique permutations
print(len(unique_strings))
# Print each unique permutation
for string in unique_strings:
print(string)
if __name__ == "__main__":
main()
Output
3 aab aba baa
Time Complexity: O(N * N!), where N is the length of input string S.
Auxiliary Space: O(N)
Contact Us