Amazon OA Question Based on Two Pointers Technique

 

amazon oa


Problem Statement:

Given two strings,searchWord and resultWord:

  • Determine the minimum number of characters you need to append to resultWord so that it becomes a subsequence of searchWord.
Example:
Input: searchWord = "abcz" resultWord = "azdb" 
Output: 2 
Explanation: By appending 'd' and 'b' to "azdb", we can transform it into a subsequence of "abcz".

Understanding the Problem:

A subsequence of a string is derived by deleting some or no characters from it without changing the order of the remaining characters. For example:

"ace" is a subsequence of "abcde" because 'a', 'c', and 'e' appear in order.
"aec" is NOT a subsequence of "abcde" because 'e' appears before 'c'.
In this problem:

Input: Two strings, searchWord and resultWord.
Output: The number of characters to append to resultWord so that all characters in resultWord appear in order as a subsequence in searchWord.

Approach to Solve the Problem

This problem can be solved efficiently using the two-pointer technique. Below is a step-by-step explanation of the approach:

  1. Two Pointers:

    • Use one pointer (i) to traverse searchWord.
    • Use another pointer (j) to traverse resultWord.
  2. Matching Characters:

    • If the character at searchWord[i] matches resultWord[j], move both pointers forward (i.e., progress to the next character in both strings).
    • If they don’t match, move only the i pointer to search for a match in the next character of searchWord.
  3. Stopping Condition:

    • The traversal stops when either:
      • All characters of searchWord have been processed.
      • All characters of resultWord have been matched.
  4. Calculate Unmatched Characters:

    • After traversal, the pointer j indicates how many characters of resultWord were matched in searchWord.
    • The unmatched characters are given by:
      unmatched = resultWord.length() - j
    • These unmatched characters are the minimum that need to be appended to resultWord.

Time and Space Complexity

  • Time Complexity:

    • The algorithm processes both strings in a single traversal.
    • Complexity: O(n + m), where n is the length of searchWord and m is the length of resultWord.
  • Space Complexity:

    • No extra space is used apart from variables.
    • Complexity: O(1).
Try to write the code by yourself if you feel anywhere stuck in this problem then comment it down👇

Comments