HackerRank in a String HackerRank Problem

Task :- Given string s, we have to determine whether the string “hackerrank” is a subsequence of the string or not.

Brute Force Approach :- If we find Longest Common Subsequence of given string s and “hackerrank” and we get LCS as “hackerrank”, then we can say that “hackerrank” is a subsequence of the given string.

This approach has time complexity of O(M*N) where M&N and length of the strings but since the second string is constant(of length 10), time complexity becomes O(N) and space complexity is also O(N).

Efficient Approach :- A better approach would be to use 2 pointers i and j which points to string s and string “hackerrank” respectively. We keep on finding the element which points to j th index in the given string at i th index , as soon as we find it we increment j and then find the next character. For eg: s = “haacckkerrannkk”

We first find “h” which is found at 0th index in the given string and then the next element “a” and so on. Look at the images below to get more clarity of the behaviours of two pointers:

1
2
3
4
5

and so on…..

When the loop completes and the value of j is 10, that means the complete string “hackerrank” is present.

This approach has time complexity of O(N) and space complexity O(1).

Code :-

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store