Javascript - How to figure out what string was inserted somewhere into a known other string?

AshleyBischoff
May 28, 2024
122 views
1 vote
2 Answers

I’m looking for the most straighforward way to figure out which string was inserted somewhere into a known other string.

Here’s what I have to work with:

I have an existing variable representing a particular string. For instance:

var originalString = "pineapple";

I also have a second variable that represents the original string after a second, unknown string has been inserted somewhere inside the first string. For instance:

var updatedString = "piBicycleneapple";

Here’s my goal:

I need some way to work backward to figure out which string was inserted into originalString to create updatedString.

Some examples:

If originalString = "pineapple" and if updatedString = "piBicycleneapple", the desired result would be "Bicycle".
If originalString = "pineapple" and if updatedString = "pineapplepear", the desired result would be "pear".

Browser support:

I’m looking for a method that works in at least the current versions of Chrome, Firefox, and Safari. So all that is to say, if by chance you had wanted to share some fancy-pants latest-ECMAScript way of doing this, that’s not necessarily a dealbreaker (as long as CanIUse or the like can confirm that that technique works in modern browsers).

Other thoughts:

I’ve brainstormed this a l’il bit, and I suppose that I could maybe use a for loop to compare originalString and updatedString character by character and then—something something—profit? But I’m not totally sure about that middle part or even whether that general approach might be overthinking it?

Answers

This might work for you :

function getNewString(originalString, updatedString) {
    let originalLength = originalString.length;
    let updatedLength = updatedString.length;
    
    // Identify the starting point where the strings start to differ
    let start = 0;
    while (start < originalLength && start < updatedLength && originalString[start] === updatedString[start]) {
        start++;
    }
    
    // Identify the ending point where the strings start to differ from the end
    let endOriginal = originalLength - 1;
    let endUpdated = updatedLength - 1;
    while (endOriginal >= start && endUpdated >= start && originalString[endOriginal] === updatedString[endUpdated]) {
        endOriginal--;
        endUpdated--;
    }
    
    // The new substring in the updatedString
    let newString = updatedString.substring(start, endUpdated + 1);
    
    return newString;
}

As @Barmar commented,

Get the difference N in length between the two strings. Step through updatedString until you get the first non-matching character. The next N characters are what was inserted.

/// Finds the index of the first difference in two array-like sequences, or the length of both sequences if they’re equal.
const findFirstDifference = (a, b) => {
    let stop = Math.min(a.length, b.length);

    for (let i = 0; i < stop; i++) {
        if (a[i] !== b[i]) {
            return i;
        }
    }

    return stop;
};

/// Finds a subsequence that can be inserted into a given original array-like sequence to produce a given updated sequence.
const getInsertion = (original, updated) => {
    let start = findFirstDifference(original, updated);
    let length = updated.length - original.length;
    return updated.slice(start, start + length);
};

console.log(getInsertion("pineapple", "piBicycleneapple"));
console.log(getInsertion("pineapple", "pineapplepear"));
console.log(getInsertion("pineapple", "pineapolitanneapple"));

Note the potential ambiguity: if the inserted string has a part in common with the original string, you won’t be able to distinguish between different rotations of it without extra information.

Please signup or login to give your own answer.

Click here to cancel reply.

Javascript – How to figure out what string was inserted somewhere into a known other string?