Longest Palindromic Subsequence of two distinct characters

Last Updated : 06 Sep, 2022

Given a string S of lowercase letters, the task is to find the length of the longest palindromic subsequence made up of two distinct characters only.

Examples:

Input: S = “bbccdcbb”
Output: 7
Explanation:
The longest palindromic subsequence of the desired form is “bbcccbb”, which is of length 7.
Input: S = “aeea”
Output: 4
Explanation:
The longest palindromic subsequence of desired form is “aeea”, which is of length 4.

Approach:
In order to solve the problem, we need to follow the steps below:

Store the number of occurrences of each character in a prefix array, and also store the position of each character in another array.
Now for each pair of equal characters calculate the maximum number of occurrences of a character between them.

Below is the implementation of the above approach:

C++

// C++ implementation to find Longest
// Palindromic Subsequence consisting
// of two distinct characters only
 
#include <bits/stdc++.h>
using namespace std;
 
// Function that prints the length of
// maximum required subsequence
void longestPalindrome(string s)
{
    // Calculate length of string
    int n = s.length();
 
    vector<vector<int> > pref(26, vector<int>(n, 0));
    vector<vector<int> > pos(26);
 
    pref[s[0] - 'a'][0]++;
    pos[s[0] - 'a'].push_back(0);
 
    // Store number of occurrences of each
    // character and position of each
    // character in string
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < 26; j++)
            pref[j][i] += pref[j][i - 1];
 
        int index = s[i] - 'a';
        pref[index][i]++;
        pos[index].push_back(i);
    }
 
    int ans = 0;
 
    // Iterate all characters
    for (int i = 0; i < 26; i++) {
 
        // Calculate number of
        // occurrences of the
        // current character
        int size = pos[i].size();
        ans = max(ans, size);
 
        // Iterate half of the
        // number of positions
        // of current character
        for (int j = 0; j < size / 2; j++) {
            int l = pos[i][j];
            int r = pos[i][size - j - 1] - 1;
 
            // Determine maximum length
            // of a character between
            // l and r position
            for (int k = 0; k < 26; k++) {
 
                int sum = pref[k][r] - pref[k][l];
 
                // Compute the maximum from all
                ans = max(ans, 2 * (j + 1) + sum);
            }
        }
    }
 
    // Printing maximum length
    cout << ans << "\n";
}
 
// Driver Code
int main()
{
    string S = "bbccdcbb";
 
    longestPalindrome(S);
 
    return 0;
}

Java

// Java implementation to find Longest
// Palindromic Subsequence consisting
// of two distinct characters only
import java.util.*;
class GFG {
 
    // Function that prints the length of
    // maximum required subsequence
    static void longestPalindrome(String s)
    {
        // Calculate length of String
        int n = s.length();
 
        int[][] pref = new int[26][n];
 
        Vector<Integer>[] pos = new Vector[26];
        for (int i = 0; i < pos.length; i++)
            pos[i] = new Vector<Integer>();
 
        pref[s.charAt(0) - 'a'][0]++;
        pos[s.charAt(0) - 'a'].add(0);
 
        // Store number of occurrences of each
        // character and position of each
        // character in String
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 26; j++)
                pref[j][i] += pref[j][i - 1];
 
            int index = s.charAt(i) - 'a';
            pref[index][i]++;
            pos[index].add(i);
        }
 
        int ans = 0;
 
        // Iterate all characters
        for (int i = 0; i < 26; i++) {
            // Calculate number of
            // occurences of the
            // current character
            int size = pos[i].size();
            ans = Math.max(ans, size);
 
            // Iterate half of the
            // number of positions
            // of current character
            for (int j = 0; j < size / 2; j++) {
                int l = pos[i].elementAt(j);
                int r = pos[i].elementAt(size - j - 1) - 1;
 
                // Determine maximum length
                // of a character between
                // l and r position
                for (int k = 0; k < 26; k++) {
                    int sum = pref[k][r] - pref[k][l];
 
                    // Compute the maximum from all
                    ans = Math.max(ans, 2 * (j + 1) + sum);
                }
            }
        }
 
        // Printing maximum length
        System.out.print(ans + "\n");
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        String S = "bbccdcbb";
        longestPalindrome(S);
    }
}
 
// This code is contributed by Princi Singh

Python3

# python3 implementation to find Longest
# Palindromic Subsequence consisting
# of two distinct characters only
 
# Function that prints the length of
# maximum required subsequence
def longestPalindrome(s):
 
    # Calculate length of string
    n = len(s)
 
    pref = [[0 for i in range(n)] for j in range(26)]
    pos = [[] for j in range(26)]
 
    pref[ord(s[0]) - ord('a')][0] += 1
    pos[ord(s[0]) - ord('a')].append(0)
 
    # Store number of occurrences of each
    # character and position of each
    # character in string
    for i in range(1,n):
        for j in range(26):
            pref[j][i] += pref[j][i - 1]
 
        index = ord(s[i]) - ord('a')
        pref[index][i] += 1
        pos[index].append(i)
 
    ans = 0
 
    # Iterate all characters
    for i in range(26):
 
        # Calculate number of
        # occurences of the
        # current character
        size = len(pos[i])
        ans = max(ans, size)
 
        # Iterate half of the
        # number of positions
        # of current character
        for j in range(size // 2):
            l = pos[i][j]
            r = pos[i][size - j - 1] - 1
 
            # Determine maximum length
            # of a character between
            # l and r position
            for k in range(26):
 
                sum = pref[k][r] - pref[k][l]
 
                # Compute the maximum from all
                ans = max(ans, 2 * (j + 1) + sum)
 
    # Printing maximum length
    print(ans)
 
# Driver Code
S = "bbccdcbb"
longestPalindrome(S)
 
# This code is contributed by shinjanpatra

C#

// C# implementation to find longest
// Palindromic Subsequence consisting
// of two distinct characters only
using System;
using System.Collections.Generic;
class GFG {
 
    // Function that prints
    // the length of maximum
    // required subsequence
    static void longestPalindrome(String s)
    {
        // Calculate length of String
        int n = s.Length;
 
        int[, ] pref = new int[26, n];
        List<int>[] pos = new List<int>[ 26 ];
 
        for (int i = 0; i < pos.Length; i++)
            pos[i] = new List<int>();
 
        pref[s[0] - 'a', 0]++;
        pos[s[0] - 'a'].Add(0);
 
        // Store number of occurrences of each
        // character and position of each
        // character in String
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 26; j++)
                pref[j, i] += pref[j, i - 1];
 
            int index = s[i] - 'a';
            pref[index, i]++;
            pos[index].Add(i);
        }
 
        int ans = 0;
 
        // Iterate all characters
        for (int i = 0; i < 26; i++) {
            // Calculate number of
            // occurences of the
            // current character
            int size = pos[i].Count;
            ans = Math.Max(ans, size);
 
            // Iterate half of the
            // number of positions
            // of current character
            for (int j = 0; j < size / 2; j++) {
                int l = pos[i][j];
                int r = pos[i][size - j - 1] - 1;
 
                // Determine maximum length
                // of a character between
                // l and r position
                for (int k = 0; k < 26; k++) {
                    int sum = pref[k, r] - pref[k, l];
 
                    // Compute the maximum from all
                    ans = Math.Max(ans, 2 * (j + 1) + sum);
                }
            }
        }
 
        // Printing maximum length
        Console.Write(ans + "\n");
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        String S = "bbccdcbb";
        longestPalindrome(S);
    }
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
 
// JavaScript implementation to find Longest
// Palindromic Subsequence consisting
// of two distinct characters only
 
// Function that prints the length of
// maximum required subsequence
function longestPalindrome(s)
{
    // Calculate length of string
    let n = s.length;
 
    let pref = new Array(26);
    for(let i = 0; i < 26; i++)
    {
        pref[i] = new Array(n).fill(0);
    }
    let pos = new Array(26);
    for(let i = 0; i < 26; i++)
    {
        pos[i] = new Array();
    }
    pref[s.charCodeAt(0) - 'a'.charCodeAt(0)][0]++;
    pos[s.charCodeAt(0) - 'a'.charCodeAt(0)].push(0);
 
    // Store number of occurrences of each
    // character and position of each
    // character in string
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < 26; j++)
            pref[j][i] += pref[j][i - 1];
 
        let index = s.charCodeAt(i) - 'a'.charCodeAt(0);
        pref[index][i]++;
        pos[index].push(i);
    }
 
    let ans = 0;
 
    // Iterate all characters
    for (let i = 0; i < 26; i++) {
 
        // Calculate number of
        // occurences of the
        // current character
        let size = pos[i].length;
        ans = Math.max(ans, size);
 
        // Iterate half of the
        // number of positions
        // of current character
        for (let j = 0; j < (size / 2); j++) {
            let l = pos[i][j];
            let r = pos[i][size - j - 1] - 1;
 
            // Determine maximum length
            // of a character between
            // l and r position
            for (let k = 0; k < 26; k++) {
 
                let sum = pref[k][r] - pref[k][l];
 
                // Compute the maximum from all
                ans = Math.max(ans, 2 * (j + 1) + sum);
            }
        }
    }
 
    // Printing maximum length
    document.write(ans,"</br>");
}
 
// Driver Code
let S = "bbccdcbb";
 
longestPalindrome(S);
 
// This code is contributed by shinjanpatra
 
</script>

Output:

Time Complexity: O(N), where N is the size of the given string.
Auxiliary Space: O(N), for creating 26 arrays of size N, the space complexity will be O(26*N) which is equivalent to O(N).

Suggest improvement

Form minimum number of Palindromic Strings from a given string

Find a number K such that Array contains at least K numbers greater than or equal to K

Share your thoughts in the comments