Amazon OA Question Based on Two Pointers Technique

 

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👇

Code Link: https://shorturl.at/lsFmP