Home » Interview coding problems/challenges

Find the largest palindromic substring using O(1) space complexity

Here, we are going to learn to find the largest palindromic substring using O(1) space complexity using the iterative approach. Submitted by Souvik Saha, on April 04, 2020

Problem statement

Given a string, you have to find the largest palindromic substring using O(1) space complexity.

    Input:
    T Test case
    T no of input string will be given to you.

    E.g.
    3
    
    abcsouuoshgcba
    includeaedulcin
    aaaaa
    
    Constrain 
    1≤ length (string) ≤100
    
    Output:
    Print the largest palindromic substring form the given string.

Example

    T=3

    Input:
    abcsouuoshgcba
    
    Output:
    souuos
    
    Input:
    includeaedulcin
    
    Output:
    cludeaedulc
    
    Input:
    aaaaa
    
    Output:
    aaaaa

Explanation with example

Let there is a string str.

Now possible arrangements are:

1. Single middle characters like aba
2. Paired middle characters like bb

To find the largest palindromic substring we follow these steps,

1. We start with the first index and go to the end of the string.
2. Every time we take two variables
3. For the first possible arrangement, we initialize the first variable with the previous index of the current index and initialize the second variable with the next index of the current index.
4. For the second possible arrangement, we initialize the first variable with the current index and initialize the second variable with the next variable of the current index.
5. If the character at the first variable place is equal with the character at the second variable place then every time we decrease the first index by one and increase the second index by one and continue the process until or unless the first variable value will be greater than or equals to zero and the second variable value will be less than the length of the string.
6. Every time we will add up two with the length of the palindrome substring count.
7. If the character at both the variable place is not the same then we compare with the palindrome substring length.

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

string count_palindrom(string str)
{
    int len = str.length();
    int max_length = 0;
    int start = 0;
    for (int i = 0; i < len; i++) {
        int j = i - 1;
        int k = i + 1;
        int count = 1;
        while (j >= 0 && k < len) {
            if (str[j] == str[k]) {
                count += 2;
                if (max_length < count) {
                    max_length = count;
                    start = j;
                }
                j--;
                k++;
            }
            else {
                break;
            }
        }
        j = i;
        k = i + 1;
        count = 0;
        while (j >= 0 && k < len) {
            if (str[j] != str[k])
                break;
            else {
                count += 2;
                if (max_length < count) {
                    max_length = count;
                    start = j;
                }
                j--;
                k++;
            }
        }
    }
    string s = "";
    if (start == 0 && max_length == 0) {
        return s + str[0];
    }
    for (int i = 0; i < max_length; i++) {
        s += str[start + i];
    }
    return s;
}

int main()
{
    //code
    int t;
    cout << "Test Case : ";
    cin >> t;
    while (t--) {
        string str;
        cout << "Enter the string : ";
        cin >> str;
        cout << "The palindromic substrings is : " << count_palindrom(str) << endl;
    }
    return 0;
}

Output

Test Case : 3
Enter the string : abcsouuoshgcba
The palindromic substrings is : souuos
Enter the string : includeaedulcin
The palindromic substrings is : cludeaedulc
Enter the string : aaaaa
The palindromic substrings is : aaaaa