Given two strings A and B, the problem is to find if string B will be a subsequence of string A if we remove the substring [A[i]..A[j]] from string A. Assume that there are Q queries giving the indices i and j and each query is independent of the other.
Examples:
Input : A = abcabcxy, B = acy
Q = 2
i = 2, j = 5
i = 3, j = 6
Output :
Yes
No
Explanation :
In the first query we remove A[2]..A[5],
getting acxy and acy is its subsequence.
In the second query we remove A[3]..A[6],
getting abxy but acy is not its subsequence.
A brute force approach is, for each query remove the required substring from A and check if B is a subsequence of A, but is inefficient because we have to modify the string A for each query and also check if string B is its subsequence.
A more efficient approach is to do preprocessing on the strings as we have to encounter multiple queries. We can store the number of characters of string B that matches till each index of string A in both the forward and backward directions, in two separate arrays. Finally we can say the answer is Yes, if the following equation holds, otherwise No:
forward[i-1] + backward[j+1] >= length(B).
This works because we are removing A[i]..A[j] from A and want to know the sum of number of characters of B that match in A
from A[1]..A[i-1] and A[j+1]..A[len], which is a subsequence if this sum is atleast the length of string B.
Following is the implementation of the above approach:
C++
// CPP program for answering queries to check// whether a string subsequence or not after// removing a substring.#include <bits/stdc++.h>using namespace std;// arrays to store results of preprocessingint *fwd, *bwd;// function to preprocess the stringsvoid preProcess(string a, string b){ int n = a.size(); // Allocate memory for fwd and bwd, and // initialize it as 0. fwd = new int[n](); bwd = new int[n](); int j = 0; // store subsequence count in forward direction for (int i = 1; i <= a.size(); i++) { if (j < b.size() && a[i - 1] == b[j]) j++; // store number of matches till now fwd[i] = j; } j = 0; // store subsequence count in backward direction for (int i = a.size(); i >= 1; i--) { if (j < b.size() && a[i - 1] == b[b.size() - j - 1]) j++; // store number of matches till now bwd[i] = j; }}// function that gives the outputvoid query(string a, string b, int x, int y){ // length of remaining string A is less // than B's length if ((x - 1 + a.size() - y) < b.size()) { cout << "No\n"; return; } if (fwd[x - 1] + bwd[y + 1] >= b.size()) cout << "Yes\n"; else cout << "No\n";}// driver functionint main(){ string a = "abcabcxy", b = "acy"; preProcess(a, b); // two queries int x = 2, y = 5; query(a, b, x, y); x = 3, y = 6; query(a, b, x, y); return 0;} |
Java
// Java program for answering // queries to check whether // a String subsequence or // not after removing a substring. class GFG { // arrays to store results // of preprocessing static int[] fwd = new int[100]; static int[] bwd = new int[100]; // function to preprocess // the strings static void preProcess(String a, String b) { int n = a.length(); // initialize it as 0. int j = 0; // store subsequence count // in forward direction for (int i = 1; i <= a.length(); i++) { if (j < b.length() && a.charAt(i - 1) == b.charAt(j)) { j++; } // store number of // matches till now fwd[i] = j; } j = 0; // store subsequence count // in backward direction for (int i = a.length(); i >= 1; i--) { if (j < b.length() && a.charAt(i - 1) == b.charAt(b.length() - j - 1)) { j++; } // store number of // matches till now bwd[i] = j; } } // function that gives // the output static void query(String a, String b, int x, int y) { // length of remaining // String A is less // than B's length if ((x - 1 + a.length() - y) < b.length()) { System.out.print("No\n"); return; } if (fwd[x - 1] + bwd[y + 1] >= b.length()) { System.out.print("Yes\n"); } else { System.out.print("No\n"); } } // Driver Code public static void main(String[] args) { String a = "abcabcxy", b = "acy"; preProcess(a, b); // two queries int x = 2, y = 5; query(a, b, x, y); x = 3; y = 6; query(a, b, x, y); }} // This code is contributed by 29AjayKumar |
Python3
# Python3 program for answering# queries to check whether# a String subsequence or# not after removing a substring.# arrays to store results# of preprocessingfwd = [0] * 100bwd = [0] * 100# function to preprocess# the stringsdef preProcess(a, b): n = len(a) # initialize it as 0. j = 0 # store subsequence count # in forward direction for i in range(1, len(a) + 1): if j < len(b) and a[i - 1] == b[j]: j += 1 # store number of # matches till now fwd[i] = j j = 0 # store subsequence count # in backward direction for i in range(len(a), 0, -1): if (j < len(b) and a[i - 1] == b[len(b) - j - 1]): j += 1 # store number of # matches till now bwd[i] = j# function that gives# the outputdef query(a, b, x, y): # length of remaining # String A is less # than B's length if (x - 1 + len(a) - y) < len(b): print("No") return if (fwd[x - 1] + bwd[y + 1]) >= len(b): print("Yes") else: print("No")# Driver Codeif __name__ == "__main__": a = "abcabcxy" b = "acy" preProcess(a, b) x = 2 y = 5 query(a, b, x, y) x = 3 y = 6 query(a, b, x, y)# This code is contributed by# sanjeev2552 |
C#
// C# program for answering // queries to check whether // a string subsequence or // not after removing a substring.using System;class GFG{ // arrays to store results // of preprocessing static int []fwd = new int[100]; static int []bwd = new int[100]; // function to preprocess // the strings static void preProcess(string a, string b) { int n = a.Length; // initialize it as 0. int j = 0; // store subsequence count // in forward direction for (int i = 1; i <= a.Length; i++) { if (j < b.Length && a[i - 1] == b[j]) j++; // store number of // matches till now fwd[i] = j; } j = 0; // store subsequence count // in backward direction for (int i = a.Length; i >= 1; i--) { if (j < b.Length && a[i - 1] == b[b.Length - j - 1]) j++; // store number of // matches till now bwd[i] = j; } } // function that gives // the output static void query(string a, string b, int x, int y) { // length of remaining // string A is less // than B's length if ((x - 1 + a.Length - y) < b.Length) { Console.Write("No\n"); return; } if (fwd[x - 1] + bwd[y + 1] >= b.Length) Console.Write("Yes\n"); else Console.Write("No\n"); } // Driver Code static void Main() { string a = "abcabcxy", b = "acy"; preProcess(a, b); // two queries int x = 2, y = 5; query(a, b, x, y); x = 3; y = 6; query(a, b, x, y); }}// This code is contributed by // Manish Shaw(manishshaw1) |
Javascript
<script>// Javascript program for answering // queries to check whether // a String subsequence or // not after removing a substring. // arrays to store results // of preprocessing let fwd = new Array(100);let bwd = new Array(100);// function to preprocess // the strings function preProcess(a,b){ let n = a.length; // initialize it as 0. let j = 0; // store subsequence count // in forward direction for (let i = 1; i <= a.length; i++) { if (j < b.length && a[i - 1] == b[j]) { j++; } // store number of // matches till now fwd[i] = j; } j = 0; // store subsequence count // in backward direction for (let i = a.length; i >= 1; i--) { if (j < b.length && a[i-1] == b[b.length - j - 1]) { j++; } // store number of // matches till now bwd[i] = j; }}// function that gives // the output function query(a,b,x,y){ // length of remaining // String A is less // than B's length if ((x - 1 + a.length - y) < b.length) { document.write("No<br>"); return; } if (fwd[x - 1] + bwd[y + 1] >= b.length) { document.write("Yes<br>"); } else { document.write("No<br>"); }}// Driver Code let a = "abcabcxy", b = "acy";preProcess(a, b);// two queries let x = 2, y = 5;query(a, b, x, y);x = 3;y = 6;query(a, b, x, y);// This code is contributed by rag2127</script> |
Output
Yes No
The time complexity of the above approach is O(n + q), where q is the number of queries and n is the length of string A.
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!
