Permutation – HackerEarth Problem Solution And Editorial

Problem name: Permutation.

Platform: HackerEarth.

Difficulty: Easy.

Solution method: Breadth-First Search

Click here to see the problem statement.

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. }