C++: LLPS

Thought Process

To find the lexicographically largest palindromic substring (LLPS), we need to identify the largest character in the string. We use a frequency array of size 26 (for each lowercase letter) & count the frequency of each character. Then, we iterate from the end of the frequency array to find the largest character and print it along with its count. This creates the longest possible palindromic substring with the largest possible character. 

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

int main(){

    string str;
    cin >> str; // woowwoww

    int arr[26] = {0};
    for(int i=0;i<str.size();i++){

        char ch = str[i];
        arr[ch-'a']++;
    }

    for(int i=25;i>=0;i--){
        if(arr[i]!=0){

            while(arr[i]!=0){
                cout << (char)('a'+i);
                arr[i]--;
            }
            cout << endl;
            break;
        }
    }
    return 0;
}

Code Complexity

Time Complexity: O(n)

The algorithm iterates through the string once to count character frequencies and then iterates through the frequency array, resulting in a linear time complexity.

Space Complexity: O(1)

The algorithm uses a constant amount of extra space (a frequency array of size 26) to store character counts.

Code copied!