PM2B editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest

Author: Chandan Boruah
Tester: Chandan Boruah
Editorialist: Chandan Boruah

DIFFICULTY:

EASY

PREREQUISITES:

DP

PROBLEM:

Given a string, find all possible unique strings that can be formed by permutation of the characters in the string.

QUICK EXPLANATION:

Create all possible permutations of the string using recursion and store all the strings formed in a linked list. If the string is unique and the length of the string is equal to the length of the original string increment counter.

EXPLANATION:

Create all possible permutations using a recursive function. Start with all possible indexes in the string and swap with other positions in the string, and put it to the recursion. Add to a linked list all the strings formed. After the function returns all the values, print all the unique strings formed that are equal in length to the original string. (Note: There might be other methods as well).

AUTHOR’S SOLUTION IN C#:

using System;
using System.Collections.Generic;
class some
{
	public static List<string>done,ll;
	public static void Main()
	{
		int n=int.Parse(Console.ReadLine());
		while((n--)>0)
		{
			done=new List<string>();
			ll=new List<string>();
			string a=Console.ReadLine();
			ll.Add(a);
			int count=0;
			for(int i=0;i<a.Length;i++)
				solve(a,i);	
			foreach(string kk in ll)
			{
				if(kk.Length==a.Length)
					count++;
			}
			Console.WriteLine(count);
		}
	}
	public static void solve(string t,int ind)
	{
		if(done.Contains(t+" "+ind))return;
		char[]tt=t.ToCharArray();
		int nn=0;
		for(int i=ind+1;i<t.Length;i++)
		{
			char cc=tt[ind];
			tt[ind]=tt[i];
			tt[i]=cc;
			string p=new string(tt);
			if(!ll.Contains(p))
			{
				ll.Add(p);
				solve(p,i);
				
			}tt=t.ToCharArray();
		}
		done.Add(t+" "+ind);
	}
}