Longest subsequence with different adjacent characters
Last Updated :
24 Jul, 2023
Given string str. The task is to find the longest subsequence of str such that all the characters adjacent to each other in the subsequence are different.
Examples:
Input: str = “ababa”
Output: 5
Explanation:
“ababa” is the subsequence satisfying the condition
Input: str = “xxxxy”
Output: 2
Explanation:
“xy” is the subsequence satisfying the condition
Method 1: Greedy Approach
It can be observed that choosing the first character which is not similar to the previously chosen character given the longest subsequence of the given string with different adjacent characters.
The idea is to keep track of previously picked characters while iterating through the string, and if the current character is different from the previous character, then count the current character to find the longest subsequence.
Implementation:
C++
#include <bits/stdc++.h>
using namespace std;
int longestSubsequence(string s)
{
int n = s.length();
int answer = 0;
char prev = '-';
for (int i = 0; i < n; i++) {
if (prev != s[i]) {
prev = s[i];
answer++;
}
}
return answer;
}
int main()
{
string str = "ababa";
cout << longestSubsequence(str);
return 0;
}
|
Java
import java.util.*;
class GFG {
static int longestSubsequence(String s)
{
int n = s.length();
int answer = 0;
char prev = '-';
for (int i = 0; i < n; i++) {
if (prev != s.charAt(i)) {
prev = s.charAt(i);
answer++;
}
}
return answer;
}
public static void main(String[] args)
{
String str = "ababa";
System.out.print(longestSubsequence(str));
}
}
|
Python3
def longestSubsequence(s):
n = len(s)
answer = 0
prev = '-'
for i in range(0, n):
if (prev != s[i]):
prev = s[i]
answer += 1
return answer
str = "ababa"
print(longestSubsequence(str))
|
C#
using System;
class GFG {
static int longestSubsequence(String s)
{
int n = s.Length;
int answer = 0;
char prev = '-';
for (int i = 0; i < n; i++) {
if (prev != s[i]) {
prev = s[i];
answer++;
}
}
return answer;
}
public static void Main(String[] args)
{
String str = "ababa";
Console.Write(longestSubsequence(str));
}
}
|
Javascript
<script>
function longestSubsequence(s)
{
var n = s.length;
var answer = 0;
var prev = '-';
for (var i = 0; i < n; i++) {
if (prev != s[i]) {
prev = s[i];
answer++;
}
}
return answer;
}
var str = "ababa";
document.write( longestSubsequence(str));
</script>
|
Time Complexity: O(N), where N is the length of the given string.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Method 2: Dynamic Programming
- For each character in the given string str, do the following:
- Choose the current characters in the string for the resultant subsequence and recur for the remaining string to find the next possible characters for the resultant subsequence.
- Omit the current characters and recur for the remaining string to find the next possible characters for the resultant subsequence.
- The maximum value in the above recursive call will be the longest subsequence with different adjacent elements.
- The recurrence relation is given by:
Let dp[pos][prev] be the length of longest subsequence
till index pos such that alphabet prev was picked previously.a dp[pos][prev] = max(1 + function(pos+1, s[pos] - 'a' + 1, s),
function(pos+1, prev, s));
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int dp[100005][27];
int calculate(int pos, int prev, string& s)
{
if (pos == s.length()) {
return 0;
}
if (dp[pos][prev] != -1)
return dp[pos][prev];
int val = 0;
if (s[pos] - 'a' + 1 != prev) {
val = max(val,
1 + calculate(pos + 1,
s[pos] - 'a' + 1,
s));
}
val = max(val, calculate(pos + 1, prev, s));
return dp[pos][prev] = val;
}
int longestSubsequence(string s)
{
int n = s.length();
memset(dp, -1, sizeof(dp));
return calculate(0, 0, s);
}
int main()
{
string str = "ababa";
cout << longestSubsequence(str);
return 0;
}
|
Java
class GFG{
static int dp[][] = new int[100005][27];
static int calculate(int pos, int prev, String s)
{
if (pos == s.length())
{
return 0;
}
if (dp[pos][prev] != -1)
return dp[pos][prev];
int val = 0;
if (s.charAt(pos) - 'a' + 1 != prev)
{
val = Math.max(val, 1 + calculate(pos + 1,
s.charAt(pos) - 'a' + 1,
s));
}
val = Math.max(val, calculate(pos + 1, prev, s));
return dp[pos][prev] = val;
}
static int longestSubsequence(String s)
{
int n = s.length();
for(int i = 0; i < 100005; i++)
{
for (int j = 0; j < 27; j++)
{
dp[i][j] = -1;
}
}
return calculate(0, 0, s);
}
public static void main(String[] args)
{
String str = "ababa";
System.out.print(longestSubsequence(str));
}
}
|
Python3
dp = [[-1 for i in range(27)] for j in range(100005)];
def calculate(pos, prev, s):
if (pos == len(s)):
return 0;
if (dp[pos][prev] != -1):
return dp[pos][prev];
val = 0;
if (ord(s[pos]) - ord('a') + 1 != prev):
val = max(val, 1 + calculate(pos + 1,
ord(s[pos]) -
ord('a') + 1, s));
val = max(val, calculate(pos + 1, prev, s));
dp[pos][prev] = val;
return dp[pos][prev];
def longestSubsequence(s):
n = len(s);
return calculate(0, 0, s);
if __name__ == '__main__':
str = "ababa";
print(longestSubsequence(str));
|
C#
using System;
public class GFG{
static int [,]dp = new int[100005,27];
static int calculate(int pos, int prev, String s)
{
if (pos == s.Length)
{
return 0;
}
if (dp[pos,prev] != -1)
return dp[pos,prev];
int val = 0;
if (s[pos] - 'a' + 1 != prev)
{
val = Math.Max(val, 1 +
calculate(pos + 1,
s[pos] - 'a' + 1,
s));
}
val = Math.Max(val, calculate(pos + 1, prev, s));
return dp[pos,prev] = val;
}
static int longestSubsequence(String s)
{
int n = s.Length;
for(int i = 0; i < 100005; i++)
{
for (int j = 0; j < 27; j++)
{
dp[i,j] = -1;
}
}
return calculate(0, 0, s);
}
public static void Main(String[] args)
{
String str = "ababa";
Console.Write(longestSubsequence(str));
}
}
|
Javascript
<script>
let dp = new Array(100005);
function calculate(pos, prev, s)
{
if (pos == s.length)
{
return 0;
}
if (dp[pos][prev] != -1)
return dp[pos][prev];
let val = 0;
if (s[pos].charCodeAt() - 'a'.charCodeAt() + 1 != prev)
{
val = Math.max(val, 1 + calculate(pos + 1,
s[pos].charCodeAt() - 'a'.charCodeAt() + 1,
s));
}
val = Math.max(val, calculate(pos + 1, prev, s));
dp[pos][prev] = val;
return dp[pos][prev];
}
function longestSubsequence(s)
{
let n = s.length;
for(let i = 0; i < 100005; i++)
{
dp[i] = new Array(27);
for (let j = 0; j < 27; j++)
{
dp[i][j] = -1;
}
}
return calculate(0, 0, s);
}
let str = "ababa";
document.write(longestSubsequence(str));
</script>
|
Time Complexity: O(N), where N is the length of the given string.
Auxiliary Space: O(26*N) where N is the length of the given string.
Approach 2: Using DP Tabulation method ( Iterative approach )
The approach to solving this problem is the same but DP tabulation(bottom-up) method is better then Dp + memorization(top-down) because memorization method needs extra stack space of recursion calls.
Steps to solve this problem:
- Create a vector to store the solution of the subproblems.
- Initialize the table with base cases
- Fill up the table iteratively
- Return the final solution
Implementation:
C++
#include <bits/stdc++.h>
using namespace std;
int longestSubsequence(string s)
{
int n = s.length();
int dp[n + 1][27];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= 26; j++) {
dp[i][j] = 0;
}
}
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j <= 26; j++) {
if (s[i] - 'a' + 1 != j) {
dp[i][j] = 1 + dp[i + 1][s[i] - 'a' + 1];
}
dp[i][j] = max(dp[i][j], dp[i + 1][j]);
}
}
return dp[0][0];
}
int main()
{
string str = "ababa";
cout << longestSubsequence(str);
return 0;
}
|
Java
import java.util.Arrays;
public class Main {
static int longestSubsequence(String s)
{
int n = s.length();
int[][] dp = new int[n + 1][27];
for (int i = 0; i <= n; i++) {
Arrays.fill(dp[i], 0);
}
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j <= 26; j++) {
if (s.charAt(i) - 'a' + 1 != j) {
dp[i][j] = 1
+ dp[i + 1]
[s.charAt(i) - 'a' + 1];
}
dp[i][j] = Math.max(dp[i][j], dp[i + 1][j]);
}
}
return dp[0][0];
}
public static void main(String[] args)
{
String str = "ababa";
System.out.println(longestSubsequence(str));
}
}
|
Python3
def longestSubsequence(s):
n = len(s)
dp = [[0 for j in range(27)] for i in range(n+1)]
for i in range(n+1):
for j in range(27):
dp[i][j] = 0
for i in range(n-1, -1, -1):
for j in range(27):
if ord(s[i]) - ord('a') + 1 != j:
dp[i][j] = 1 + dp[i+1][ord(s[i])-ord('a')+1]
dp[i][j] = max(dp[i][j], dp[i+1][j])
return dp[0][0]
if __name__ == '__main__':
str = "ababa"
print(longestSubsequence(str))
|
C#
using System;
public class Solution
{
public static int LongestSubsequence(string s)
{
int n = s.Length;
int[, ] dp = new int[n + 1, 27];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= 26; j++) {
dp[i, j] = 0;
}
}
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j <= 26; j++) {
if (s[i] - 'a' + 1 != j) {
dp[i, j]
= 1 + dp[i + 1, s[i] - 'a' + 1];
}
dp[i, j] = Math.Max(dp[i, j], dp[i + 1, j]);
}
}
return dp[0, 0];
}
public static void Main(string[] args)
{
string str = "ababa";
Console.WriteLine(LongestSubsequence(str));
}
}
|
Javascript
function longestSubsequence(s) {
let n = s.length;
let dp = Array.from(Array(n+1), () => new Array(27).fill(0));
for (let i = n-1; i >= 0; i--) {
for (let j = 0; j <= 26; j++) {
if (s.charCodeAt(i) - 'a'.charCodeAt(0) + 1 != j) {
dp[i][j] = 1 + dp[i+1][s.charCodeAt(i)-'a'.charCodeAt(0)+1];
}
dp[i][j] = Math.max(dp[i][j], dp[i+1][j]);
}
}
return dp[0][0];
}
let str = "ababa";
console.log(longestSubsequence(str));
|
Time Complexity: O(N), where N is the length of the given string.
Auxiliary Space: O(N) where N is the length of the given string.
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...