3460. Longest Common Prefix After at Most One Removal 🔒

Problem Description

You are given two strings s and t. Your task is to determine the length of the longest common prefix between s and t after removing at most one character from s. Note that it is permissible to leave s without any removal.

Intuition

To solve this problem, we use a two-pointer technique. Begin by pointing to the start of both strings s and t with two pointers, i and j. As we traverse these strings, we want to match characters in sequence to find a common prefix.

The key challenge is to calculate the longest common prefix while allowing for the possible removal of a single character from s. We introduce a boolean flag, rem, to track whether a character has been removed.

During traversal, if the characters at the current pointers are equal (s[i] == t[j]), it indicates part of a common prefix, and both pointers are advanced. If the characters differ, there are two scenarios:

If no character has been removed yet (rem is False), we toggle the rem flag to True to represent that one character from s can be skipped. Thus, we only advance the pointer i on string s without increasing j.
If the rem is already True, indicating we've already skipped a character, the common prefix ends, and we break the loop.

The traversal continues until one of the strings is completely processed (i exceeds n or j exceeds m). The length of the common prefix is indicated by the position of j, since it reflects how many characters of t form part of the prefix with s.

Learn more about Two Pointers patterns.

Solution Approach

The solution employs a Two Pointers technique with a boolean flag to manage the possible removal of one character from the string s.

Initialization:
- Determine the lengths of s and t, storing them in n and m respectively.
- Initialize two pointers, i and j, to the beginning of s and t.
- Introduce a boolean variable rem set to False to indicate whether a character removal has already occurred.
Traverse both strings:
- Use a while loop to iterate as long as both pointers are within the bounds of their respective strings (i < n and j < m).
- Inside the loop, check if the characters at the current pointers are equal:
  - If s[i] == t[j], increment both i and j to continue matching the prefix.
- If the characters differ (s[i] != t[j]):
  - Check if any character has been removed (rem is True):
    - If a character has already been removed, break the loop since the longest common prefix with a single removal has been determined.
  - If no character has been removed (rem is False):
    - Set rem to True to indicate a removal.
    - Increment i to consider skipping the character from s and reevaluate the match without advancing j.
Return the result:
- After exiting the loop, return j as it indicates the length of the common prefix. The pointer j reflects how far into t a common prefix is maintained with s.

This approach ensures we efficiently examine the potential of removing one character from s while finding the longest common prefix.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a simple example to illustrate the solution approach:

Suppose we have two strings:

s = "abcdef"
t = "abcxef"

Our task is to determine the longest common prefix between s and t after potentially removing at most one character from s.

Step-by-step Execution:

Initialization:
- Lengths: n = 6 (for s), m = 6 (for t).
- Pointers: i = 0 (for s), j = 0 (for t).
- Flag: rem = False (no character removed yet).
Traversal:
- First Iteration:
  - Compare s[i] = 'a' with t[j] = 'a'. They match.
  - Increment both pointers: i = 1, j = 1.
- Second Iteration:
  - Compare s[i] = 'b' with t[j] = 'b'. They match.
  - Increment both pointers: i = 2, j = 2.
- Third Iteration:
  - Compare s[i] = 'c' with t[j] = 'c'. They match.
  - Increment both pointers: i = 3, j = 3.
- Fourth Iteration:
  - Compare s[i] = 'd' with t[j] = 'x'. They don't match.
  - Since rem is False, toggle rem to True.
  - Skip s[i] by incrementing i = 4, retaining j = 3.
- Fifth Iteration:
  - Compare s[i] = 'e' with t[j] = 'x'. They don't match and rem is True.
  - Break the loop since we've already skipped one character.
Return the Result:
- The value of j is 3, indicating the longest common prefix up to the third character ("abc").

In this example, removing d from s allows the longest common prefix with t to be "abc", giving a prefix length of 3.

Solution Implementation

1class Solution:
2    def longestCommonPrefix(self, s: str, t: str) -> int:
3        n, m = len(s), len(t)  # Get lengths of both strings
4        i = j = 0  # Initialize pointers for each string
5        mismatch_occurred = False  # Flag to indicate if a mismatch has occurred
6
7        # Iterate through the strings while both pointers are within bounds
8        while i < n and j < m:
9            # Check if characters at current pointers are not equal
10            if s[i] != t[j]:
11                if mismatch_occurred:  # If a mismatch has already occurred, break the loop
12                    break
13                mismatch_occurred = True  # Set the flag as a mismatch has happened
14            else:
15                j += 1  # Increment the second string pointer if characters match
16            i += 1  # Always increment the first string pointer
17
18        return j  # Return the length of the longest common prefix found so far
19

1class Solution {
2    public int longestCommonPrefix(String s, String t) {
3        int sLength = s.length(); // Length of the first string
4        int tLength = t.length(); // Length of the second string
5        int indexS = 0; // Pointer for first string
6        int indexT = 0; // Pointer for second string
7        boolean mismatchFound = false; // Flag to track if a mismatch has occurred
8
9        // Loop through both strings until we reach the end of one of them
10        while (indexS < sLength && indexT < tLength) {
11            // If characters at the current position don't match
12            if (s.charAt(indexS) != t.charAt(indexT)) {
13                // If a mismatch has already been found, break out of the loop
14                if (mismatchFound) {
15                    break;
16                }
17                // Mark that a mismatch has occurred
18                mismatchFound = true;
19            } else {
20                // If the characters match, move the second string pointer
21                indexT++;
22            }
23            // Always move the first string pointer
24            indexS++;
25        }
26
27        // Return the length of the longest common prefix found
28        return indexT;
29    }
30}
31

1class Solution {
2public:
3    // Function to find the length of the longest common prefix between two strings
4    int longestCommonPrefix(std::string s, std::string t) {
5        int lenS = s.length(); // Length of string s
6        int lenT = t.length(); // Length of string t
7        int indexS = 0, indexT = 0; // Initialize indices for iterating through both strings
8        bool mismatchOccurred = false; // Flag to check if a mismatch has been encountered yet
9
10        // Iterate while there are characters left in both strings
11        while (indexS < lenS && indexT < lenT) {
12            // If characters at current position do not match
13            if (s[indexS] != t[indexT]) {
14                // If a mismatch was previously found, break from the loop
15                if (mismatchOccurred) {
16                    break;
17                }
18                // Mark that a mismatch has occurred
19                mismatchOccurred = true;
20            } else {
21                // If characters match, move to the next character in string t
22                ++indexT;
23            }
24            // Move to the next character in string s
25            ++indexS;
26        }
27        // Return the length of the longest common prefix
28        return indexT;
29    }
30};
31

1// Finds the length of the longest common prefix between two strings 's' and 't'
2function longestCommonPrefix(s: string, t: string): number {
3    // Get the lengths of the input strings
4    const [n, m] = [s.length, t.length];
5  
6    // Initialize pointers for both strings and a flag to track character mismatch
7    let [i, j] = [0, 0];
8    let rem: boolean = false;
9
10    // Loop through both strings while pointers are within lengths
11    while (i < n && j < m) {
12        // If characters at current positions do not match
13        if (s[i] !== t[j]) {
14            // Check if there was already a character mismatch
15            if (rem) {
16                // Break if a previous mismatch was already encountered
17                break;
18            }
19            // Set the flag to true as a mismatch is found
20            rem = true;
21        } else {
22            // Increment the pointer for string 't' on matching characters
23            ++j;
24        }
25        // Always increment the pointer for string 's'
26        ++i;
27    }
28
29    // Return the number of characters matched for the longest common prefix
30    return j;
31}
32

Time and Space Complexity

The time complexity of the code is O(n + m), where n is the length of string s and m is the length of string t. This is because the algorithm compares each character of both strings up to the length of the shorter string until a mismatch is found or the end of one of the strings is reached.

The space complexity of the code is O(1) because the algorithm uses a constant amount of additional space for variables i, j, and rem, regardless of the input size.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which of the following problems can be solved with backtracking (select multiple)

Generating subsets

Generating random numbers

Generating permutations

Sorting integers