Nitishkumar's Blog

DAY 2 (2nd time)

Nitishkumar's photo
Nitishkumar
·

4 min read

Problem Statement (podt : All Unique Permutations of an array: Medium level)

Given an array arr[] of length n. Find all possible unique permutations of the array in sorted order. A sequence A is greater than sequence B if there is an index i for which Aj = Bj for all j<i and Ai > Bi.

Input: 
n = 3
arr[] = {1, 2, 1}
Output: 
1 1 2
1 2 1
2 1 1
Explanation:
These are the only possible unique permutations
for the given array.

This is a backtracking problem. Here we are taking an array arr , a vector to save 1 permutation,then another vector freq of size n and initialize it to 0, then a set of vectors to save the unique permutation.

First Base case, if size of ds is equal to arr size then store the ds in the set,
then we have a for loop from 0 to arr, inside which we have to check if the freq is 0 or 1 if it's 0 then add that element to ds then change freq from 0 to 1 and then call the function . After which change freq back to 0 and remove element from ds . so what we are doing here is we are accepting element once and not accepting element in another case , this resulting in taking all permutation.

void solve(vector<int>&arr,vector<int>&ds,vector<int>&freq,set<vector<int>>&ans,int n)
    {
        if(ds.size()==arr.size())
        {
            vector<int> temp;
            for(auto it:ds)
            {
                temp.push_back(it);
            }
            ans.insert(temp);
            return ;
        }
        for(int i=0;i<arr.size();i++)
        {
            if(!freq[i])
            {
                ds.push_back(arr[i]);
                freq[i]=1;
                solve(arr,ds,freq,ans,n);
                freq[i]=0;
                ds.pop_back();
            }
        }
    }
    vector<vector<int>> uniquePerms(vector<int> &arr ,int n) {
        // sort(arr.begin(),arr.end());
        set<vector<int>> ans;
        vector<int> ds;
        vector<int> freq(n,0);
        solve(arr,ds,freq,ans,n);
        vector<vector<int>>res;
        for(auto it: ans)
        {
            res.push_back(it);
        }
        return res;

    }

There are multiple alternative methods for this problem

vector<vector<int>> uniquePerms(vector<int> &arr ,int n) {
        vector<vector<int>>res;
        sort(arr.begin(),arr.end());
        do{
            res.push_back(arr);
        }while(next_permutation(arr.begin(),arr.end()));
        return res;
    }

here we are using builtin function next_permutation();

Problem Statement (easy: Check if frequencies can be equal ) IMP

Given a string s which contains only lower alphabetic characters, check if it is possible to remove at most one character from this string in such a way that frequency of each distinct character becomes same in the string.

s = xyyz
Output: 1 
Explanation: Removing one 'y' will make 
frequency of each letter 1.

here I will take 2 map 1 to hold the index and it's frequency and in another we take frequency as key and frequency of frequency as value . Crazy right....

then check if second map size is 2 or less than 2 if it's greater then return false . if size is 2 then store the frequency in a vector and check one of the 2 elements should be one and the difference between the values should be 1.

bool sameFreq(string s)
    {
        vector<int> vec1,vec2;
        unordered_map<char,int> mp1;
        unordered_map<int,int> mp2;
        int len = s.length();
        for(int i =0;i<len;i++)
        {
           mp1[s[i]]++; 
        }
        for(auto it:mp1)
        {
            mp2[it.second]++;
        }
        if(mp2.size()==1)
        {
            return true;
        }
        else if(mp2.size()==2)
        {
            for(auto it:mp2)
            {
               vec1.push_back(it.first);
               vec2.push_back(it.second);
            }
            int maxvec = max(vec1[0],vec1[1]);
            int minvec = min(vec1[0],vec1[1]);
            if(mp2[minvec]==1 && minvec==1)
            {
                return true;
            }
            else if((vec1[1]-vec1[0]==1 || vec1[0]-vec1[1]==1) && mp2[maxvec] ==1)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
        else
        {
            return false;
        }   
    }

Problem Statement (easy: Min Number of Flips)

Given a binary string, that is it contains only 0s and 1s. We need to make this string a sequence of alternate characters by flipping some of the bits, our goal is to minimize the number of bits to be flipped.

Input:
S = "001"
Output: 1
Explanation: 
We can flip the 0th bit to 1 to have
101.

In this problem we take 2 integers where 1 counts the changes when first element is 0 and another counts when first element is 1 then we compare both and return the variable which is minimum.

int minFlips (string s)
{
    // your code here
    int c1=0,c2=0;

    for(int i=0;i<s.size();i++)
    {
        if(i%2==0){
            if(s[i]=='1')
                c1++;
            else
                c2++;

        }
        else if(i%2==1){
            if(s[i]=='0')
                c1++;
            else
                c2++;
        }

    }
    return(min(c1,c2));

}

Played football for an hour today as the outdoor activity.

podtGfgpermutations