HackerRank in a String HackerRank Problem
HackerRank in a String! | HackerRank
Determine if a string contains a subsequence of characters that spell "hackerrank".
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:
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).