Longest Common Prefix After at Most One Removal

Longest Common Prefix After at Most One Removal - Problem

You are given two strings s and t. Return the length of the longest common prefix between s and t after removing at most one character from s.

Note: s can be left without any removal.

Input & Output

Example 1 — Basic Mismatch

$ Input: s = "abcde", t = "abfgh"

› Output: 2

💡 Note: The common prefix without removal is "ab" (length 2). Removing any character from s doesn't improve this, so the answer is 2.

Example 2 — Remove to Extend

$ Input: s = "axbc", t = "abc"

› Output: 3

💡 Note: Without removal: common prefix is "a" (length 1). Removing s[1]='x' gives "abc" vs "abc", common prefix "abc" (length 3).

Example 3 — No Improvement

$ Input: s = "abc", t = "def"

› Output: 0

💡 Note: No common prefix exists regardless of removal. The answer is 0.

Constraints

1 ≤ s.length, t.length ≤ 1000
s and t consist of only lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Two strings s and t to compare

Process

Find mismatch and try skipping one character from s

Output

Length of longest possible common prefix

Key Takeaway

🎯 Key Insight: When characters mismatch, try skipping the problematic character to potentially extend the common prefix

Asked in

M Microsoft 25 G Google 18

The key insight is to find where strings first differ, then try skipping that character in s. The two pointers approach efficiently handles this by avoiding string reconstruction. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n²)	O(n)	Try removing each character from s and find the longest common prefix
Two Pointers Optimization	O(n)	O(1)	Use two pointers to efficiently handle the mismatch case

Brute Force — Algorithm Steps

Try with no character removed from s
Try removing character at each position i
For each attempt, calculate common prefix length with t
Return the maximum length found

Visualization

Tap to expand

Step-by-Step Walkthrough

No Removal

Compare original strings directly

Try Each Removal

Remove one character at a time from s

Find Maximum

Return the longest prefix found

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int commonPrefixLength(const char* str1, const char* str2) {
    int i = 0;
    while (str1[i] && str2[i] && str1[i] == str2[i]) {
        i++;
    }
    return i;
}

int solution(const char* s, const char* t) {
    int maxLength = 0;
    int sLen = strlen(s);
    
    // Try without removing any character
    int length = commonPrefixLength(s, t);
    if (length > maxLength) maxLength = length;
    
    // Try removing each character from s
    char* modifiedS = malloc(sLen);
    for (int i = 0; i < sLen; i++) {
        // Create modified string without character at position i
        strncpy(modifiedS, s, i);
        strcpy(modifiedS + i, s + i + 1);
        
        length = commonPrefixLength(modifiedS, t);
        if (length > maxLength) maxLength = length;
    }
    
    free(modifiedS);
    return maxLength;
}

int main() {
    char s[1001], t[1001];
    fgets(s, sizeof(s), stdin);
    fgets(t, sizeof(t), stdin);
    
    // Remove newline characters
    s[strcspn(s, "\n")] = 0;
    t[strcspn(t, "\n")] = 0;
    
    int result = solution(s, t);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n+1 attempts (no removal + n removals), we compare up to n characters

⚠ Quadratic Growth

Space Complexity

O(n)

Creating modified strings for each removal attempt

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler