Teaching Kids Programming – Remove One Letter to Transform to Another

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given two strings s0 and s1, return whether you can obtain s1 by removing 1 letter from s0.

Constraints
0 ≤ n ≤ 200,000 where n is the length of s0
0 ≤ m ≤ 200,000 where m is the length of `s1
Example 1
Input
s0 = “hello”
s1 = “hello”
Output
False

Example 2
Input
s0 = “hello”
s1 = “helo”
Output
True

Hint #1
Try all possible ways to remove single character

Hint #2
S0.length==S1.length+1

Hint #3
If the condition S0.length==S1.length+1 meet, we just need to check is string S1 is the subsequence of string S0

Remove One Letter via Check SubSequence Algorithm

First, we check if the length differs one – and then we just have to check if s1 is subsequence of s0.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def removeOneLetter(self, s0, s1):
        if len(s1) + 1 != len(s0):
            return False
        def isSub(a, b):
            la, lb = len(a), len(b)
            if la > lb:
                return False
            i, j = 0, 0
            while i < la and j < lb:
                if a[i] == b[j]:
                    i += 1
                j += 1
            return i == la
        return isSub(s1, s0)

class Solution:
    def removeOneLetter(self, s0, s1):
        if len(s1) + 1 != len(s0):
            return False
        def isSub(a, b):
            la, lb = len(a), len(b)
            if la > lb:
                return False
            i, j = 0, 0
            while i < la and j < lb:
                if a[i] == b[j]:
                    i += 1
                j += 1
            return i == la
        return isSub(s1, s0)

The time complexity is O(N+M) where N and M are the lengths of two strings respectively.

Remove One Letter by Checking Characters by Characters

We can check two strings characters by characters and once there is a difference, we check the remainder substrings with one skipping one character.

1
2
3
4
5
6
7
8

class Solution:
    def removeOneLetter(self, s0, s1):
        if len(s1) + 1 != len(s0):
            return False
        for i in range(len(s1)):
            if s0[i] != s1[i]:
                return s0[i+1:] == s1[i:]
        return True

class Solution:
    def removeOneLetter(self, s0, s1):
        if len(s1) + 1 != len(s0):
            return False
        for i in range(len(s1)):
            if s0[i] != s1[i]:
                return s0[i+1:] == s1[i:]
        return True

The same complexity for time and space. See also: Can a String be Constructing by Removing a Letter from Another String?

–EOF (The Ultimate Computing & Technology Blog) —