Sherlock and the Ugly Flower — UGLYF

PROBLEM: UGLYF FOR PRACTICE : SUBMIT

Difficulty : Easy

Solution Approach: Tricky

Prerequisite: Array,Hashing,String

Problem Description:

You have two strings S1 and S2 as input .Now put them perpendicular to each other in such a way that they overlap at the same character. For example, For two strings “ABCDEF” and “XXBCZQ”, one possible way to make a flower is:

A
          B 
    X X B C Z Q
          D
          E
          F

Length of petals in the above flower are 2, 2, 3 and 3.

A flower’s ugliness is sum of absolute difference of adjacent petal lengths i.e. if adjacent petal lengths are L1, L2, L3, L4, then ugliness of flower is |L1 — L2| + |L2 — L3| + |L3 — L4| + |L4 — L1| , where | . | is the absolute function.

You have to find minimum value of ugliness on considering all possible flower configurations. Note that a configuration is valid even if any of the petal length is 0.

Solution Description:

Key point:

As there are more than one character may common in both the strings and that character may occur more than one time in the particular string .So we have to take care all the combination possible.

Approach:

1.We will use hashing using array of size 26 (for 26 alphabets of English) . Since indexing of an array starts from 0 so we have to map it with character.For that let say value at index 0 denote whether ‘a’ is present in the string or not , value at index 1 represents whether ‘b’ is present in the particular string or not and so on.

for example : Consider String “ABC” hashing will be made as array[0]=array[1]=array[2]=true and all other index have value false .

index (character)=ASCII (character)-65.

Here index(.) represents index corresponding to a character and ASCII(.) represents ascii value of a character.

2. Suppose a character occur once in a string then there is only one possible position of string to divide it .But if one character occurs more than once and then there are more than one position to divide the string .But to get minimum ugliness it should divide a string as equally as possible (i.e. the position of character is considered feasible which is closest to the middle position of string ).

3.The common character that made our solution or give flower having minimum ugliness (more than one flower possible having minimum ugliness) will have minimum distance from the middle of both the strings.

4. Four other arrays will be used (two for each string) .One of which store the position of a character closest to the middle and other will be store the distance of that position from middle (i.e. number of characters between that character and middle one).This has to be done for both the string .

EXAMPLE:

S1=”ABCDEF”

S2 = “XXBCZQ”

We assume

Index array: stores position of character closest to middle.

Offset array:stores distance of character at having index value stored in “Index array” from middle of string.

Scenario for S1 will be like this:

and for string S2 :

Note :- Our array is of length 26 but for sake of simplicity we only care about the characters present in the corresponding string.In second scenario note that the values at index [23] correspond to second X present in S2 because it is one which is closest to the middle.

5.Now the only task is remaining to find the ugliness for each possible flower.

#Flower overlapped at ‘C’ :

          A
          B 
    X X B C Z Q
          D
          E
          F

l1=2, l2=2,l3=3,l4=3;

ugliness= | l1-l2 | + | l2-l3 | + | l3-l4 | + | l4-l1 | = 0+1+0+1 = 2;

#Flower overlapped at ‘B’ :

          A
      X X B C Z Q 
          C
          D
          E
          F

l1=1 , l2=3 , l3=4 , l4=2;

ugliness= | l1-l2 | + | l2-l3 | + | l3-l4 | + | l4-l1 | = 2+1+2+1 = 6;

So the answer will be Minimum(2,6) = 2;

Code:C++

#include<iostream>
#include<string>
#include<limits.h>//for INT_MAX
#include<algorithm>
using namespace std;
int main()
{
    int t;
    cin>>t;
    string s1,s2;
    while(t--)
    {
        //input two strings
        cin>>s1>>s2;
//define arrays
        bool arr[26]={false},brr[26]={false};
        int a1[26],a2[26],b1[26],b2[26];
//find lengths of each strings
        int len1=s1.length();
        int len2=s2.length();
        //find mid index of each strings
        int mid1=(len1)/2;
        int mid2=(len2)/2;
//assign offset arrays to infinity
        for(int i=0;i<26;i++)
        {
            a1[i]=b1[i]=INT_MAX;
        }
/*fill the index of array denoted by character present in string 1
         with minimum offset of that character from middle index of string*/
        for(int i=0;i<len1;i++)
        {
            arr[s1[i]-65]=true;
if(abs(mid1-i)< a1[s1[i]-65])
            {
                a1[s1[i]-65]=abs(mid1-i);
                a2[s1[i]-65]=i;
            }
        }
/*fill the index of array denoted by character present in string 2
         with minimum offset of that character from middle index of string*/
        for(int i=0;i<len2;i++)
        {
            brr[s2[i]-65]=true;
if(abs(mid2-i)< b1[s2[i]-65])
            {
                b1[s2[i]-65]=abs(mid2-i);
                b2[s2[i]-65]=i;
            }
        }
//find comman character of both string giving minimum ugliness of the flower
        int l1,l2,l3,l4;
        int minn=INT_MAX;
        for(int i=0;i<26;i++)
        {
            if(arr[i]==true && brr[i]==true)
            {
                l1=a2[i];
                l3=len1-(a2[i]+1);
l2=b2[i];
                l4=len2-(b2[i]+1);
minn=min(minn,abs(l1-l2)+abs(l2-l3)+abs(l3-l4)+abs(l4-l1));
            }
        }
        //print minimum ugliness of the flower
        cout<<minn<<endl;
    }
    return 0;
}
#happy_coding #codebrace
If you find something wrong or have any question about the solution then comment down below, you can also contact us using  contact form