Tuesday, May 17, 2022

Easy_Question18 : Is Subsequence

  • A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. 

  • (ie, "ace" is a subsequence of "abcde" while "aec" is not).

Example 1:
  • input: s = "abc", t = "ahbgdc"
  • Output: true
Example 2:
  • Input: s = "axc", t = "ahbgdc"
  • Output: false
Solution :

public boolean isSubsequence(String s, String t) {
    if(s.length()==0)
        return true;

    int i=0;
    int j=0;    
    while(i<s.length() && j<t.length()){
        if(s.charAt(i)==t.charAt(j)){
            i++;
        }

        j++;

        if(i==s.length())
               return true;
    }
    return false;
}

Time Complexity

O(min(M , N)) as we keep iterating until i or j becomes zero. M and N are the lengths of the strings.

Space Complexity

O(1) as we use constant space in the memory.

Follow on LinkedIn

You may also like

Kubernetes AWS Java Coding Question
Microservices Core Java Spring Boot
Spring Framework Kafka Miscellaneous