Given two strings S and T of lengths n and m respectively. Find the maximum adjacent index difference for the indices where string T is present in string S as a subsequence.
- Cost is defined as the difference between indices of subsequence T
- The maximum cost of a sequence is defined as max(ai+1−ai) for 1 ≤ i < m.
- It is guaranteed that there is at least subsequence as T in S.
Examples:
Input: S = “abbbc”, T = “abc”
Output: 3
Explanation: One of the subsequences is {1, 4, 5} denoting the sequence “abc” same as T, thus the maximum cost is 4 – 1 = 3 .Input: S = “aaaaa”, T = “aa”
Output: 4
Explanation: One of the subsequences is {1, 5} and the max cost is 5 – 1 = 4 .
Approach: For some subsequence of the string S, let ai denote the position of the character Ti in the string S. For fixed i, we can find a subsequence that maximizes ai+1−ai.
Follow the below steps to solve the problem:
- Let lefti and righti be the minimum and maximum possible value of ai among all valid a’s respectively. Now, it is easy to see that the maximum possible value of ai+1 − ai is equal to righti+1 − lefti.
- To calculate lefti we just need to find the first element after lefti−1 which is equal to Ti , righti can be found in the same way by iterating in the reverse direction.
- So, after finding left and right, the answer is max(righti+1−lefti) for 1 ≤ i < m.
Below is the implementation of the above approach.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum// cost of a subsequenceint maxCost(string s, string t, int n, int m){ // mxCost stores the maximum // cost of a subsequence int mxCost = 0; // left[i] and right[i] store // the minimum and maximum // value of ai among all // valid a's respectively int left[m], right[m]; int j = 0; for (int i = 0; i < n; i++) { if (j >= m) break; if (s[i] == t[j]) { left[j] = i; j++; } } j = m - 1; for (int i = n - 1; i >= 0; i--) { if (j < 0) break; if (s[i] == t[j]) { right[j] = i; j--; } } for (int i = 0; i < m - 1; i++) { mxCost = max(mxCost, right[i + 1] - left[i]); } return mxCost;}// Driver functionint main(){ string S = "abbbc", T = "abc"; int n = S.length(), m = T.length(); // Function Call cout << maxCost(S, T, n, m); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ // Function to find the maximum // cost of a subsequence static int maxCost(String s, String t, int n, int m) { // mxCost stores the maximum // cost of a subsequence int mxCost = 0; // left[i] and right[i] store // the minimum and maximum // value of ai among all // valid a's respectively int []left = new int[m]; int []right = new int[m]; int j = 0; for (int i = 0; i < n; i++) { if (j >= m) break; if (s.charAt(i) == t.charAt(j)) { left[j] = i; j++; } } j = m - 1; for (int i = n - 1; i >= 0; i--) { if (j < 0) break; if (s.charAt(i) == t.charAt(j)) { right[j] = i; j--; } } for (int i = 0; i < m - 1; i++) { mxCost = Math.max(mxCost, right[i + 1] - left[i]); } return mxCost; } // Driver function public static void main(String[] args) { String S = "abbbc", T = "abc"; int n = S.length(), m = T.length(); // Function Call System.out.print(maxCost(S, T, n, m)); }}// This code is contributed by 29AjayKumar |
Python
# Python program for the above approach# Function to find the maximum# cost of a subsequencedef maxCost(s, t, n, m): # mxCost stores the maximum # cost of a subsequence mxCost = 0 # left[i] and right[i] store # the minimum and maximum # value of ai among all # valid a's respectively left = [] right = [] j = 0 for i in range(0, n): if (j >= m): break if (s[i] == t[j]): left.append(i) j += 1 j = m - 1 for i in reversed(range(n)): if (j < 0): break if (s[i] == t[j]): right.append(i) j -= 1 for i in range(0, m - 1): mxCost = max(mxCost, right[i + 1] - left[i]) return mxCost# Driver functionS = "abbbc"T = "abc"n = len(S)m = len(T)print(maxCost(S, T, n, m))# This code is contributed by Samim Hossain Mondal. |
C#
// C# program for the above approachusing System;class GFG{ // Function to find the maximum // cost of a subsequence static int maxCost(String s, String t, int n, int m) { // mxCost stores the maximum // cost of a subsequence int mxCost = 0; // left[i] and right[i] store // the minimum and maximum // value of ai among all // valid a's respectively int []left = new int[m]; int []right = new int[m]; int j = 0; for (int i = 0; i < n; i++) { if (j >= m) break; if (s[i] == t[j]) { left[j] = i; j++; } } j = m - 1; for (int i = n - 1; i >= 0; i--) { if (j < 0) break; if (s[i] == t[j]) { right[j] = i; j--; } } for (int i = 0; i < m - 1; i++) { mxCost = Math.Max(mxCost, right[i + 1] - left[i]); } return mxCost; } // Driver function public static void Main() { String S = "abbbc", T = "abc"; int n = S.Length, m = T.Length; // Function Call Console.Write(maxCost(S, T, n, m)); }}// This code is contributed by gfgking |
Javascript
<script> // JavaScript program for the above approach // Function to find the maximum // cost of a subsequence const maxCost = (s, t, n, m) => { // mxCost stores the maximum // cost of a subsequence let mxCost = 0; // left[i] and right[i] store // the minimum and maximum // value of ai among all // valid a's respectively let left = new Array(m).fill(0), right = new Array(m).fill(0); let j = 0; for (let i = 0; i < n; i++) { if (j >= m) break; if (s[i] == t[j]) { left[j] = i; j++; } } j = m - 1; for (let i = n - 1; i >= 0; i--) { if (j < 0) break; if (s[i] == t[j]) { right[j] = i; j--; } } for (let i = 0; i < m - 1; i++) { mxCost = Math.max(mxCost, right[i + 1] - left[i]); } return mxCost; } // Driver function let S = "abbbc", T = "abc"; let n = S.length, m = T.length; // Function Call document.write(maxCost(S, T, n, m));// This code is contributed by rakeshsahni</script> |
Output
3
Time Complexity: O(n + m)
Auxiliary Space: 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!
