Cracking The Coding Interview Together – Problem 1.5: One Away

Welcome back to the series! As always, we’re not just “solving” the problem — we’re learning how to think about the problem, how to talk through it in an interview, and how to reason about optimizations before jumping into code.

If you’re new to this series:

We always follow the format as follows

1. Understand the problem statement together
2. Ask any questions, that you would like to ask the interviewer
3. I would urge you to take your time here and try to come up with your own solution before going forward
4. Think how you would go about solving the problem(you would be talking out loud in front of the actual interviewer)
5. Write code and understand how it works and explain it to your interviewer

Problem statement

There are three types of edits that can be performed on strings: insert a character,
remove a character, or replace a character. Given two strings, write a function to check if they are one edit (or zero edits) away.

Examples

pale, ple    -> true   (remove 'a')
pales, pale  -> true   (remove 's')
pale, bale   -> true   (replace 'p' with 'b')
pale, bake   -> false

Analyse the problem statement together

Let's try to understand the problem statement, I am sure you think that this problem is tricky and difficult to solve and you wouldn't be completely wrong in thinking that. So let's make sure we understand clearly.

First things first, please understand that we are not asked to check how many edit distances away two strings are, rather we have been asked if two strings are one or zero edit distance away or not. The former problem is bit different and slightly more complex but the later one is not that complex but it is still tricky.

Two strings are one edit away if they can become equal by one insert, one delete, or one replace — or they were already equal to begin with (zero edits allowed).

The next step in the process would be to figure out how we could figure out if two strings are one edit away or one delete away or one replace away. Once we establish that we should be able to solve this problem, but let's also see if there is anything unclear and needs clarification.

Take some time and try to dig deep to see if there is anything unclear to you.

Questions for the interviewer

This is important — don’t assume. Speak clearly and ask. I have collected following questions or clarifications

If interviewer doesn’t specify, assume case sensitive, ASCII, valid non-null strings.

For this post, we assume case sensitive, no trimming, no auto-conversions.

Think about the Solution

Like always, I recommend you pause here and actually think through how you'd solve it.

Pretend you're in a real interview. You are expected to talk out loud.

Ask yourself:

• How do I compare two strings in a way that allows “one deviation”?
• When are two strings definitely not one edit away?
• How do I avoid over complicating this?

Try a few examples by hand before continuing.

First Approach: Brute Force (but logically sound)

If we approach this in the most brute-force conceptual way:

1. Generate all possible strings that are one edit away from the first string.
2. Check if the second string exists in that set.

Example: "pale"
Possible one-edit strings:

• Replace each index with 26 letters
• Insert every letter at every position
• Remove every character once

This would explode combinatorially:

• Replace: len(s) * 26
• Insert: (len(s)+1) * 26
• Remove: len(s)

That’s manageable for small strings, but in Big-O terms:

O(26 * n + 26 * (n+1) + n) ≈ O(n)
BUT generating and comparing full strings repeatedly is expensive in memory/time.

Also, this brute force looks clever but is actually a terrible interview answer, and your interviewer will immediately ask you to optimize.

Still — it’s good to think about brute force because it helps us identify the core constraints:

1. If length difference > 1 → automatic false (no need to compute anything)
2. If lengths are equal → only replace is possible
3. If lengths differ by 1 → only insert or remove possible

So even the brute force thinking gives us a rule:

if abs(len(s1) - len(s2)) > 1:
    return False

This is an important insight and you should say it out loud in an interview.

Optimized Thought Process — The Real Solution

We break the problem into three separate cases, but implement all of them in one unified function:

This gives us a decision tree:

if lengths equal:
    check one replacement
elif lengths differ by 1:
    check one insert/remove
else:
    return False

The interviewer loves this because:

1. You’re categorizing the problem correctly
2. You're not doing character frequency maps or full permutations
3. You’re reasoning based on constraints, not guesswork

How Do We Check “One Insert/Delete Away”?

Walk through both strings index by index and count how many characters differ.

p a l e
b a l e
^
difference = 1 → OK

If at any point difference > 1, return false.

Runs in O(n) time, constant memory.

How Do We Check “One Replace Away”?

The idea is simple:

• Compare both strings with two pointers.
• If characters match → move both pointers.
• If they don’t → move only the pointer of the longer string.
• If mismatch happens more than once → return false.

Example: "pales" and "pale"

p a l e s
p a l e
          ↑ pointer has moved only in the longer string

Still linear time: O(n) and constant memory

Write code and explain

Since you have the complete understanding of the solution you explain the solution and write the code. Implementation could be as follows:

public class OneAway {

    public static boolean oneEditAway(String first, String second) {
        // Quick length check
        if (Math.abs(first.length() - second.length()) > 1) {
            return false;
        }

        // Identify longer and shorter string
        String longer = first.length() >= second.length() ? first : second;
        String shorter = first.length() < second.length() ? first : second;

        int index1 = 0; // pointer for longer string
        int index2 = 0; // pointer for shorter string
        boolean foundDifference = false;

        while (index1 < longer.length() && index2 < shorter.length()) {
            if (longer.charAt(index1) != shorter.charAt(index2)) {
                if (foundDifference) {
                    return false; // already found one difference before
                }
                foundDifference = true;

                // If same length, move both pointers (replace case)
                if (longer.length() == shorter.length()) {
                    index2++;
                }
            } else {
                // Characters matched, move shorter pointer
                index2++;
            }

            // Always move pointer of longer string
            index1++;
        }

        return true;
    }

    // Quick tests
    public static void main(String[] args) {
        System.out.println(oneEditAway("pale", "ple"));     // true
        System.out.println(oneEditAway("pales", "pale"));   // true
        System.out.println(oneEditAway("pale", "bale"));    // true
        System.out.println(oneEditAway("pale", "bake"));    // false
        System.out.println(oneEditAway("a", ""));           // true
        System.out.println(oneEditAway("", "b"));           // true
        System.out.println(oneEditAway("abc", "abc"));      // true
        System.out.println(oneEditAway("pale", "paleeeee")); // false
    }
}

Let's Walk Through a Few Test Cases

Time & Space Complexity

This is as optimal as it gets.
You cannot do better than linear scan because you must examine each character at least once.

Few things worth mentioning:

• Runs in O(n) time, where n is the length of the shorter string
• Uses O(1) space — no extra arrays, maps, or string building
• Single unified function handles replace, insert, and delete
• Uses pointer-based scan, which is the cleanest optimal solution

Final Thoughts

Next Sunday we continue with 1.6 — String Compression.

As always, I urge you to actually try implementing today's problem in your own editor before that.

If you're following the series, drop a comment, share how you're practicing, or even send me your own solution — I love seeing variations.

Until next time — happy coding, and keep cracking interviews together. 🚀

Happy Coding!