Determine if a string is a subsequence of another string
Given two strings, check if the second string is a subsequence of the first string.
A subsequence is a sequence that can be obtained by deleting some characters from a string without changing the relative order of the other characters. For example,
Output: true
Explanation: abd is a subsequence of abcde
Input: first = abcde, second = acb
Output: false
Explanation: acb is not a subsequence of abcde
The idea is very simple: simultaneously traverse both strings and compare the current character of the first string with the next character of the second string, both starting from the beginning. We increment the pointer of the first string at each iteration of the loop and increment the second string’s pointer only if a match is found. We return true if the end of the second string is reached at any time and false otherwise.
Following is the C++, Java, and Python implementation based on the idea:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include <iostream> #include <string> using namespace std; bool isSubsequence(string first, string second) { // base case: an empty string is a subsequence of any string if (second.empty()) { return true; } // index for the next character of the second string int i = 0; // iterate over each character of the first string for (char c: first) { // if the current character matches the next character of the second string if (c == second[i]) { // return true if we reach end of the second string if (++i == second.length()) { return true; } } } // we reach here only if second string is not a subsequence of first string return false; } int main() { string first = "abcde"; string second = "abd"; if (isSubsequence(first, second)) { cout << "Subsequence found"; } else { cout << "Not a subsequence"; } return 0; } |
Output:
Subsequence found
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
class Main { public static boolean isSubsequence(String first, String second) { // base case: an empty string is a subsequence of any string if (second.isEmpty()) { return true; } // index for the next character of the second string int i = 0; // iterate over each character of the first string for (char c: first.toCharArray()) { // if the current character matches the next character of the second string if (c == second.charAt(i)) { // return true if we reach end of the second string if (++i == second.length()) { return true; } } } // we reach here only if second string is not a subsequence of first string return false; } public static void main(String[] args) { String first = "abcde"; String second = "abd"; if (isSubsequence(first, second)) { System.out.println("Subsequence found"); } else { System.out.println("Not a subsequence"); } } } |
Output:
Subsequence found
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
def isSubsequence(first, second): # base case: an empty string is a subsequence of any string if not second: return True # index for the next character of the second string i = 0 # iterate over each character of the first string for c in first: # if the current character matches the next character of the second string if c == second[i]: # increment the index and return true if end of second string is reached i = i + 1 if i == len(second): return True # we reach here only if second string is not a subsequence of first string return False if __name__ == '__main__': first = 'abcde' second = 'abd' if isSubsequence(first, second): print('Subsequence found') else: print('Not a subsequence') |
Output:
Subsequence found
The time complexity of the above solution is O(n) where n is the length of the string.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)