Author Arunima Mandal

Longest Palindromic Substring

Arunima Mandal Leave a comment

Note: The problem title is pretty self-explaining. Now as for the solution, it can be solved in the usual brute force method (for each starting and ending position) in O(N^3) time. Another way would be Dynamic Programming which results in O(N^2) for both time complexity and space complexity.

The following approach is also an intuitive one (though hard to come to mind at first) with better time and space complexities. It is called Expand Around Centre.

Since expanding a palindrome around its center could take O(n) time, and as we are expanding for every index of the string, the overall complexity is O(n^2). And the space complexity is O(1).

Code:

#include <bits/stdc++.h>

using namespace std;

int expandAroundCentre(string &s, int left, int right)
{
    while(left>=0 && right<s.size() && s[left]==s[right])
    {
        left--;
        right++;
    }
    return right-left-1;
}

string longestPalindrome(string s)
{
    if(s.size()==0) return "";
    int start=0, ans=0;
    for(int i=0; i<s.size(); i++)
    {
        int len1=expandAroundCentre(s,i,i); //for odd length
        int len2=expandAroundCentre(s,i,i+1); //for even length
        int len=max(len1,len2);
        if(len>ans) //if len is greater than previous palindromic length
        {
            start=i-(len-1)/2; //for left side of i
            ans=len;
        }
    }
    return s.substr(start,ans);
}

int main()
{
    string s;
    cin>>s;
    cout<<"The longest palndromic substring is "<<longestPalindrome(s)<<endl;
    return 0;
}

Maximum Sum SubArray Problem

Arunima Mandal Leave a comment

Approach 1: Kadane’s Algorithm

Though it’s a particular algorithm, if one is good at programming, this approach is more intuitive than any other approach without knowing that this is actually an algorithm! 

#include<bits/stdc++.h>

using namespace std;

int maxSumSubArray(int a[], int size)
{
    int max_so_far = INT_MIN, max_ending_here = 0, start =0, end = 0, s=0;
    //cout<<"max_so_far "<<max_so_far<<endl;

    for (int i=0; i< size; i++ )
    {
        max_ending_here += a[i];

        if (max_ending_here > max_so_far)
        {
            max_so_far = max_ending_here;
            start = s;
            end = i;
        }

        if (max_ending_here < 0)   ///If that is any negative number, we discard it
        {
            max_ending_here = 0;
            s = i+1; ///and start considering from the next index.That is we are rightfully assuming
                    ///that the beginning & ending of the subsequence can't contain any negative number.
        }
    }
    cout << "Maximum contiguous sum is "
        << max_so_far << endl;
    cout << "Starting index "<< start
        << endl << "Ending index "<< end << endl;
}

/*Driver program to test maxSumSubArray*/
int main()
{
    int a[] = {-2, -3, 4, -1, -2, 1, 5, -3};
    int n = sizeof(a)/sizeof(a[0]);
    int max_sum = maxSumSubArray(a, n);
    return 0;
}

If the problem states that the subarray would have to be of k size, fear not! That solution is not much different from the above approach. We have just to modify the above solution a bit in that case.

#include<bits/stdc++.h>

using namespace std;

int maxSumSubArray(int a[], int size, int k)
{
    if(k>size) cout<<"Invalid"<<endl;

    int sum=0,maxi=-100000,start=0,endi;
    for(int i=0;i<k;i++) sum+=a[i];
    maxi=sum;
    for (int i=k; i< size; i++ )
    {
        sum+= a[i]-a[i-k];
        if(sum>maxi)
        {
            maxi=sum;
            start= i-k+1;
            endi=i;
        }
    }
    cout<<"Maximum sum "<<maxi<<endl;
    cout<<"Start at index "<<start<<" and ends at index "<<endi<<endl;
    return maxi;

}

/*Driver program to test maxSumSubArray*/
int main()
{
    int a[] = {-2, -3, 4, -1, -2, 1, 5, -3};
    int k=3;
    int n = sizeof(a)/sizeof(a[0]);
    int max_sum = maxSumSubArray(a, n, k);
    return 0;
}

Approach 2: Using DP(Dynamic Programming)

This method is also intuitive for solving the problem if one is comfortable using the DP algorithm.

#include <bits/stdc++.h>

using namespace std;

int maxSumSubArray_dp(int nums[], int size)
{
    int dp[100005]= {0};
    dp[0] = nums[0];
    int maxi = dp[0];
    for (int i = 1; i < size; i++)
    {
        dp[i] = max(dp[i - 1] + nums[i], nums[i]);
        maxi = max(maxi, dp[i]); // find max in dp
    }
    return maxi;
}

int main()
{
    int nums[] = {-2, -3, 4, -1, -2, 1, 5, -3};
    int n = sizeof(nums)/sizeof(nums[0]);
    int max_sum = maxSumSubArray_dp(nums, n);
    cout<<"Maximum Sum Subarray using DP is "<<max_sum<<endl;
    return 0;
}

Longest Common Prefix of a String

Arunima Mandal Leave a comment

Brute-Force (Vertical Scanning):

Here we are returning an empty string if no common prefix is found.

Time Complexity: O(S) where S is the sum of all characters present in the vector. Or we can say O(mn) where m is the length of the vector and n is the length of the strings (assuming of highest limit) inside the vector.

Space Complexity: O(1) as constant space for the answer only.

#include <bits/stdc++.h>

using namespace std;

string longestCommonPrefix(vector<string>& strs) {
    string ans="";
    for(int j=0; j<strs[0].size(); j++)
    {
        char ch=strs[0][j];
        for(int i=1; i<strs.size(); i++)
        {
            if(j>=strs[i].size() || strs[i][j]!=ch)
            {
                return ans;
            }
        }
        ans+=ch;
    }
    return ans;
}

int main()
{
    vector<string> v;
    int n;
    cout << "Enter the no. of string you want to compare" << endl;
    cin>>n;
    cout<<"Enter the strings"<<endl;
    string s;
    for(int i=0; i<n; i++)
    {
        cin>>s;
        v.push_back(s);
    }
    cout<<"The longest common prefix is "<<longestCommonPrefix(v)<<endl;
    return 0;
}

Binary Search:

The trick to using the binary search in this problem is to find out the minimum length string first, and then apply binary search to it.

Time Complexity: O(S*log(n)) where S is the sum of all characters in the vector and n is the size of the length of the minimum string.

Space complexity: O(1).

#include <bits/stdc++.h>

using namespace std;

bool isCommonPrefix(vector<string>& strs, int len)
{
    string s=strs[0].substr(0,len);
    for(int i=1; i<strs.size(); i++)
    {
        if(strs[i].substr(0,len)!=s) return false;
    }
    return true;
}

string longestCommonPrefix(vector<string>& strs) {
    string mini_str;
    int mini=300;
    for(int i=0; i<strs.size(); i++)
    {
        if(strs[i].size()<mini)
        {
            mini=strs[i].size();
            mini_str=strs[i];
        }
    }
    if(mini==0) return "";

    int low=1; //Can't initialize it to 0 as we are considering length
    int high=mini;
    while(low<=high)
    {
        int mid=low+(high-low)/2;
        if(isCommonPrefix(strs, mid)) low=mid+1;
        else high=mid-1;
    }
    return strs[0].substr(0,(high+low)/2);
}


int main()
{
    vector<string> v;
    int n;
    cout << "Enter the no. of string you want to compare" << endl;
    cin>>n;
    cout<<"Enter the strings"<<endl;
    string s;
    for(int i=0; i<n; i++)
    {
        cin>>s;
        v.push_back(s);
    }
    cout<<"The longest common prefix is "<<longestCommonPrefix(v)<<endl;
    return 0;
}

Palindrome check of an Integer without converting it to a string

Arunima Mandal Leave a comment

Note: The first idea while checking a palindrome that comes to our mind is converting the integer to a string and then reversing it. And then comparing that two strings. But that takes extra space. But if we can check without converting the integer to a string, then both time and space complexity decrease for sure.

The below code is for input -2^31 < x < 2^31.

Time complexity: O(ceil (size of the integer / 2 )). That means O(1) as constant time.
Space complexity: O(1).

#include <bits/stdc++.h>

using namespace std;

bool isPalindrome(int x)
{
    if(x<0 || (x!=0 && x%10==0)) return false;
    int num=x, reverted_num_half=0;
    while(reverted_num_half < num)
    {
        int residue=num%10;
        num=num/10;
        reverted_num_half=(reverted_num_half*10)+residue;
    }
    if(num==reverted_num_half/10 || num==reverted_num_half) return true;
    else return false;
}

int main()
{
    int x=1;
    while(x!=0)
    {
        cout << "Enter an integer" << endl;
        cin>>x;
        if(isPalindrome(x)==1) cout<<"Palindrome"<<endl;
        else cout<<"Not palindrome"<<endl;
        cout<<endl;
    }

    return 0;
}

Topological Sorting: Kahn’s algorithm

Arunima Mandal Leave a comment

This algorithm requires no Queue or Stack.

#include <bits/stdc++.h>
#define MAX  2000

using namespace std;

vector<int> topSort(int node, vector<int> &indeg, vector<vector<int> > &adj)
{
    vector<int> ans;
    for(int i=0; i<node; i++) //Inserting all independent nodes first
    {
        if(indeg[i]==0) ans.push_back(i);
    }

    for(int i=0; i<ans.size(); i++)
    {
        int u=ans[i];
        for(int j=0; j<adj[u].size(); j++)
        {
            int v=adj[u][j];
            indeg[v]--;
            if(indeg[v]==0) ans.push_back(v);
        }
    }
    if(ans.size()!=node) ans.clear(); //cycle found, so returning empty vector
    return ans;
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

    int node, edge;
    cout<<"Enter the number of nodes and edges: ";

    while(cin>>node>>edge) //assuming node>=0, edges>=0
    {
        vector<int> indeg(node,0);
        vector<vector<int> > adj(node);
        /* //for string input
        unordered_map<string,int> mp;
        unordered_map<int,string> mp;
        int c=0;
        */

        if(edge==0) //Print all nodes as all are independent
        {
            for(int i=0; i<node; i++) cout<<i<<" ";
            cout<<endl;
        }

        cout<<"Enter the relations(pair of edges): "<<endl;

        for(int i=0; i<edge; i++) //Populating Adjacency list and indeg array for TopSort
        {
            int from,to;
            //string from,to;
            cin>>from>>to;

            /* //Processing string input

            if(mp1[from]==0)
            {
                mp1[from]=++c;
                mp2[c]=from;
            }
            if(mp1[to]==0)
            {
                mp1[to]=++c;
                mp2[c]=to;
            }
            g[mp1[from]].pb(mp1[to]);
            indeg[mp1[to]]++;
            */
            adj[from].push_back(to);
            indeg[to]++;
        }

        vector<int> ans=topSort(node, indeg, adj);

        if(ans.size()>0) //Ordering possible
        {
            cout<<"The correct ordering is:";
            for(int i=0; i<ans.size(); i++)
            {
                cout<<" "<<ans[i];
                //cout<<mp2[ans[i]]<<" ";
            }
            cout<<endl;
        }
        else cout<<"Cycle exists"<<endl; //Ordering not possible
    }
    return 0;
}