First String is a Subsequence of second using Two Pointers (Iterative)
The idea is to use two pointers, one pointer will start from start of str1 and another will start from start of str2. If current character on both the indexes are same then increment both pointers otherwise increment the pointer which is pointing str2.
Follow the steps below to solve the problem:
- Initialize the pointers i and j with zero, where i is the pointer to str1 and j is the pointer to str2.
- If str1[i] = str2[j] then increment both i and j by 1.
- Otherwise, increment only j by 1.
- If i reaches the end of str1 then return TRUE else return FALSE.
Below is the implementation of the above approach
C++
/*Iterative C++ program to check If a string is subsequence of another string*/ #include <bits/stdc++.h> using namespace std; /*Returns true if s1 is subsequence of s2*/ bool issubsequence(string& s1, string& s2) { int n = s1.length(), m = s2.length(); int i = 0, j = 0; while (i < n && j < m) { if (s1[i] == s2[j]) i++; j++; } /*If i reaches end of s1,that mean we found all characters of s1 in s2, so s1 is subsequence of s2, else not*/ return i == n; } int main() { string s1 = "gksrek" ; string s2 = "w3wiki" ; if (issubsequence(s1, s2)) cout << "gksrek is subsequence of w3wiki" << endl; else cout << "gksrek is not a subsequence of " "w3wiki" << endl; return 0; } |
Java
/*package whatever //do not write package name here */ import java.io.*; import java.util.*; class GFG { /*Iterative Java program to check If a String is subsequence of another String*/ /*Returns true if s1 is subsequence of s2*/ static boolean issubsequence(String s1, String s2) { int n = s1.length(), m = s2.length(); int i = 0 , j = 0 ; while (i < n && j < m) { if (s1.charAt(i) == s2.charAt(j)) i++; j++; } /*If i reaches end of s1,that mean we found all characters of s1 in s2, so s1 is subsequence of s2, else not*/ return i == n; } public static void main(String args[]) { String s1 = "gksrek" ; String s2 = "w3wiki" ; if (issubsequence(s1, s2)) System.out.println( "gksrek is subsequence of geekforgeeks" ); else System.out.println( "gksrek is not a subsequence of geekforgeeks" ); } } // This code is contributed by shinjanpatra. |
Python3
# Iterative JavaScript program to check # If a string is subsequence of another string # Returns true if s1 is subsequence of s2 def issubsequence(s1, s2): n, m = len (s1), len (s2) i, j = 0 , 0 while (i < n and j < m): if (s1[i] = = s2[j]): i + = 1 j + = 1 # If i reaches end of s1,that mean we found all # characters of s1 in s2, # so s1 is subsequence of s2, else not return i = = n # driver code s1 = "gksrek" s2 = "w3wiki" if (issubsequence(s1, s2)): print ( "gksrek is subsequence of geekforgeeks" ) else : print ( "gksrek is not a subsequence of geekforgeeks" ) # This code is contributed by shinjanpatra |
C#
// C# code to implement the approach using System; class GFG { /*Returns true if s1 is subsequence of s2*/ static bool issubsequence( string s1, string s2) { int n = s1.Length, m = s2.Length; int i = 0, j = 0; while (i < n && j < m) { if (s1[i] == s2[j]) i++; j++; } /*If i reaches end of s1,that mean we found all characters of s1 in s2, so s1 is subsequence of s2, else not*/ return i == n; } public static void Main( string [] args) { string s1 = "gksrek" ; string s2 = "w3wiki" ; if (issubsequence(s1, s2)) Console.WriteLine(s1 + " is subsequence of " + s2); else Console.WriteLine( s1 + " is not a subsequence of " + s2); } } // This code is contributed by phasing17. |
Javascript
<script> /*Iterative JavaScript program to check If a string is subsequence of another string*/ /*Returns true if s1 is subsequence of s2*/ function issubsequence(s1, s2) { let n = s1.length, m = s2.length; let i = 0, j = 0; while (i < n && j < m) { if (s1[i] == s2[j]) i++; j++; } /*If i reaches end of s1,that mean we found all characters of s1 in s2, so s1 is subsequence of s2, else not*/ return i == n; } // driver code let s1 = "gksrek" ; let s2 = "w3wiki" ; if (issubsequence(s1, s2)) document.write( "gksrek is subsequence of geekforgeeks" , "</br>" ); else document.write( "gksrek is not a subsequence of geekforgeeks" , "</br>" ); // This code is contributed by shinjanpatra </script> |
gksrek is subsequence of w3wiki
Time Complexity: O(max(n,m)), where n,m is the length of given string s1 and s2 respectively.
Auxiliary Space: O(1)
Given two strings, find if first string is a Subsequence of second
Given two strings str1 and str2, find if the first string is a Subsequence of the second string, i.e. if str1 is a subsequence of str2.
A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.
Examples :
Input: str1 = “AXY”, str2 = “ADXCPY”
Output: True (str1 is a subsequence of str2)Input: str1 = “AXY”, str2 = “YADXCP”
Output: False (str1 is not a subsequence of str2)Input: str1 = “gksrek”, str2 = “w3wiki”
Output: True (str1 is a subsequence of str2)