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 subsequencevoid 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 Codeint main(){ string S = "bbccdcbb"; longestPalindrome(S); return 0;} |
Java
// Java implementation to find Longest// Palindromic Subsequence consisting// of two distinct characters onlyimport 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 subsequencedef 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 CodeS = "bbccdcbb"longestPalindrome(S)# This code is contributed by shinjanpatra |
C#
// C# implementation to find longest// Palindromic Subsequence consisting// of two distinct characters onlyusing 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 subsequencefunction 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 Codelet S = "bbccdcbb";longestPalindrome(S);// This code is contributed by shinjanpatra</script> |
Output:
7
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).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
