UVa - 1209 - Wordfish Solution ( With Methods To Solve ) [ C++ Code ]

=>Try Yourself First. For help Scroll Down .

Hi .... How are you? Today I am going to Post the Way to Solve a very interesting Data Structure problem. Let's have it.

Clearance :

As the Problem Statement says you have to Find 21 permutation of the Given String where the Given String should be in the Middle of all the Permutations.You have to find out the Minimum Absolute Difference between the letters . Then find the Maximum of the Difference & Print it along That string whose minimum letter Difference is Maximum . So, what do you think ? You have to find all the Permutations . NO... Just a little Trick you have to Follow. 

Algorithm :

• As you have to keep the Given String in the Middle of the Permutation List. Take a <vector> of String. Use the STL prev_permutation() to generate The previous 10 permutation of the Given String & Store these Permutations . Then store the Given String . Now use the next_permutation() to generate next 10 Permutations of the Given String . So you have a Total of 10 + 1 + 10 = 21  Permutations .  

• From these Permutations ... For every permutations in the list, Find out the Minimum Absolute Difference between the letters . Then find the Maximum of the Difference & Print it along That string whose minimum letter Difference is Maximum .

For Instance : 

• " WORDFISH " - 21 Permutations in the Problem Statement . From these , " WORDHSFI " - has the Minimum letter the Difference which is Maximum from all the Minimum Difference of 3. That's why Answer is WORDHSFI3 .  

• Here letter difference is : - | W - O | = 9 , | O - R | = 3 , | R - D | = 15, | D - H | = 5, | H - S | = 12, | S - F | = 14 , | F - I | = 3 . ( So , the Minimum is 3 )  

Brain Storming : 

So here is the Brain Storming for this Problem . You know you have to find the Permutations . So, The permutation of N is N! ... 

Let the Length of Given String is N . Let N = 1, 2, 3, 4, 5, 6 ......... So permutation Results = 1, 2, 6, 24, 120, 720....   As you have to Find out the 21 Permutations. So,  The String Length of Greater than 3 is Okay . What if the String Length is Less than/ Equal to 3? That will you have to Find out .

Way to get AC : 

To get AC Verdict take a Special Care of Output Formation & Comparing System .

******************************** HOPE YOU SOLVED IT ALREADY *******************************

Code :

#include<bits/stdc++.h>

using namespace std;

int mintot( string s, int sz)
{
    int small = INT_MAX;
    for(int i=0; i<sz-1; i++)
    {
        small = min(small, abs((int)s[i] - (int)s[i+1]));
    }
    return small;
}

int main()
{
    string str, str2, res_str;
    while(getline(cin, str))
    {
        str2 = str;
        int maxlength = INT_MIN, len;
        int sz = str.size();
        len = mintot(str, sz);
        if(len>maxlength)
        {
            maxlength = len;
            res_str = str;
        }
        for(int i=1; i<11 ; i++)
        {
            if(prev_permutation(str.begin(), str.end()))
            {
                len = mintot(str, sz);
                if(len>maxlength)
                {
                    maxlength = len;
                    res_str = str;
                }
                if(len==maxlength)
                {
                    res_str = min(str, res_str);
                }
            }
        }
        for(int i=1; i<11; i++)
        {
            if(next_permutation(str2.begin(), str2.end()))
            {
                len = mintot(str2, sz);
                if(len>maxlength)
                {
                    maxlength = len;
                    res_str = str2;
                }
            }
        }
        cout<<res_str<<maxlength<<endl;
    }
    return 0;
} 

=>Question or Need Help ?? Leave a Comment .