 # Permutation – HackerEarth Problem Solution And Editorial

Problem name: Permutation.

Platform: HackerEarth.

Difficulty: Easy.

Post Contents

## Solution Idea For Permutation HackerEarth Problem

It is a straight-cut Breadth-First Search (BFS) example. But you have to take a queue of strings and use a map for an easier solution.

At first, take the given input for permutation in a character variable. Then insert the characters in a string. Let’s take another string and copy the given string on that string. Then sort the new string in ascending order. This is our required string. We have to find out the minimum move to find the sorted string from the given string. So, we can run a BFS to find out the smallest number of reverse operations among the substrings to find out the required sorted string. We will run our BFS loop until we found the sorted required string. Each time we will reverse the current string elements from the first element to the second to the last element. On each operation, we will check that is the substring is visited or not. If not then we will put the map value for that string +1 from the main string. We will continue the operation until we find and label the sorted required string.

Try to solve the problem on your own. After trying your best and taking your time if you were unable to find out the solution to this problem. Look at my code.

## My Code To Solve The HackerEarth Problem Permutation Using BFS:

1. /* ANTHOR KUMAR DAS
2. KUET ECE 2K18*/
3. #include<bits/stdc++.h>
4. using namespace std;
5. #define ll long long
6. #define sc(a) scanf(“%d”,&a)
7. #define sc1(n) scanf(“%lld”,&n)
8. #define tc ll tc; sc1(tc);while(tc–)
9. #define sc2(b,c) scanf(“%lld%lld”,&b,&c)
10. #define f(a,c,b) for(a=c;a<b;a++)
11. #define pb(a) push_back(a)
12. #define pf push_front
13. #define p(k) printf(“%lldn”,k)
14. #define pt printf
15. #define en printf(“n”)
16. #define br break
17. #define dot(m) cout<<fixed<<setprecision(10)<<m<<endl
18. #define co continue
19. #define sc3(s) scanf(“%s”,&s)
20. #define ye cout<<“YES”<<endl
21. #define mp(a,b) make_pair(a,b)
22. #define mm memset
23. #define ss second
24. #define ff first
25. #define no cout<<“NO”<<endl
26. #define valid(x,y,row,col) (x>=1&&x<=row&&y>=1&&y<=col)
27. #define pii pair<ll,ll>
28. ll fx[]= {0,0,1,-1};
29. ll fy[]= {1,-1,0,0};
30. ll gcdd(ll a, ll b)
31. {
32.     if(a==0)
33.     {
34.         return b;
35.     }
36.     while(b!=0)
37.     {
38.         if(a>b)
39.         {
40.             a-=b;
41.         }
42.         else
43.         {
44.             b-=a;
45.         }
46.     }
47.     return a;
48. }
49. int main()
50. {
51.     ll n,m,t,j,i,l,z=0;
52.     bool ans=false;
53.     string s=””,cp;
54.     char ch;
55.     sc1(n);
56.     f(i,0,n)
57.     {
58.         cin>>ch;
59.         s+=ch;
60.     }
61.     map<string, ll>mp;
62.     mp[s]=0;
63.     queue<string>q;
64.     q.push(s);
65.     cp=s;
66.     sort(cp.begin(),cp.end());
67.     while(q.size()>0)
68.     {
69.         string st=q.front();
70.         q.pop();
71.         if(ans)
72.             br;
73.         f(i,2,n+1)
74.         {
75.             string ss=st;
76.             reverse(ss.begin(),ss.begin()+i);
77.             if(mp[ss]==0)
78.             {
79.                 mp[ss]=mp[st]+1;
80.                 cout<<“level of “<<ss<<“=”<<mp[ss]<<endl;
81.                 if(ss==cp)
82.                 {
83.                     ans=true;
84.                     br;
85.                 }
86.                 q.push(ss);
87.             }
88.         }
89.     }
90.     p(mp[cp]);
91.     return 0;
92. }
Sample input:
5
4 5 2 3 1
Output:
4
See the execution of our Breadth-First Search loop how ss is stored in the queue q with its level for a better understanding of how the code works.
level of 54231=1
level of 25431=1
level of 32541=1
level of 13254=1
level of 45231=2
level of 24531=2
level of 32451=2
level of 13245=2
level of 52431=2
level of 34521=2
level of 13452=2
level of 23541=2
level of 52341=2
level of 14523=2
level of 31254=2
level of 23154=2
level of 52314=2
level of 42531=3
level of 35421=3
level of 13542=3
level of 23451=3
level of 42351=3
level of 15423=3
level of 31245=3
level of 23145=3
level of 42315=3
level of 34251=3
level of 13425=3
level of 43521=3
level of 54321=3
level of 12543=3
level of 31452=3
level of 43152=3
level of 54312=3
level of 53241=3
level of 45321=3
level of 14532=3
level of 25341=3
level of 43251=3
level of 14325=3
level of 41523=3
level of 54123=3
level of 25413=3
level of 21354=3
level of 52134=3
level of 45213=3
level of 32154=3
level of 51324=3
level of 45132=3
level of 25314=3
level of 32514=3
level of 41325=3
level of 35241=4
level of 13524=4
level of 53421=4
level of 12453=4
level of 31542=4
level of 53142=4
level of 45312=4
level of 15432=4
level of 24351=4
level of 15324=4
level of 51423=4
level of 45123=4
level of 24513=4
level of 21345=4
level of 42135=4
level of 54213=4
level of 32145=4
level of 54132=4
level of 24315=4
level of 32415=4
level of 15243=4
level of 31425=4
level of 43125=4
level of 12534=4
level of 12345=4

Also, don’t forget to check this UVA Online Judge problem tutorial for Breadth First Search practice.