The O(n) Club: Longest String Chain — The O(n) Club Edition

The O(n) Club: Longest String Chain — The Interview Jenga That Breaks Spirits

⚡ TL;DR

Find the biggest possible chain where each word is built by adding one new letter to the previous (no unscrambling, thank you). Brute force exists if you’re into pain and recursion, but DP plus a map sorts your life out. See both—don’t do the first.

// Brute-force. Only do this if your CPU needs a workout.
int maxChain = 1;
for (String word : words)
    maxChain = Math.max(maxChain, dfs(word)); // Wildly inefficient!
 // DP map solution — This is what your interviewer wants
Map<String, Integer> dp = new HashMap<>();
Arrays.sort(words, Comparator.comparingInt(String::length));
for (String word : words)
    for (int i = 0; i < word.length(); ++i)
        dp.put(word, Math.max(dp.getOrDefault(word, 1), dp.getOrDefault(word.substring(0, i) + word.substring(i + 1), 0) + 1));

🧠 How Devs Usually Mess This Up

Some devs try to play Scrabble logic and rearrange letters (“cat” magically becomes “tac”!). No such fun allowed: insert-only, in-order. Others build chains starting with the longest words — and end up sobbing in a heap of null because their DP map is about as useful as a dictionary with blank pages.
If you don’t process words by length, you’re just reinventing recursion hell.

🔍 What’s Actually Going On

Imagine building a word skyscraper, but you’re only allowed to slap in one new brick at a time (no Tetris-flipping!). Short words go at the bottom. Each new story needs to be just one letter longer than the last, and letters must stay where they are: “cat” can become “cart”, but not “tac”. Dynamic programming lets you climb the tower safely: for every word, check all possible ways you could’ve deleted one letter to get a shorter word you’ve already built. If you find such a predecessor, you’re standing on its metaphorical shoulders, updating your chain’s length like a polite acrobat.

🛠️ PseudoCode

• Sort words by length
  

  Arrays.sort(words, Comparator.comparingInt(String::length));

  So all possible predecessor words come before their descendants. Can’t build a castle without a foundation.
• Initialize DP map
  

  Map<String, Integer> dp = new HashMap<>();

  Working memory: dp.get(word) is chain length ending at ‘word’.
• For each word, try every possible one-letter-deletion
  

  for (int i = 0; i < word.length(); ++i) {
    String prev = word.substring(0,i) + word.substring(i+1);
    int possibleLen = dp.getOrDefault(prev, 0) + 1;
    dp.put(word, Math.max(dp.getOrDefault(word, 1), possibleLen));
  }

  This checks if chopping out each letter produces a word you’ve already handled.
• Track the best chain overall
  

  int max = 0;
  for (String word : words) max = Math.max(max, dp.get(word));

  Because one of your stacks will be the actual Leaning Tower.

💻 The Code

import java.util.*;
 public class LongestStringChain {
    public int longestStrChain(String[] words) {
        Arrays.sort(words, Comparator.comparingInt(String::length));
        Map<String, Integer> dp = new HashMap<>();
        int max = 0;
        for (String word : words) {
            int best = 1;
            for (int i = 0; i < word.length(); ++i) {
                String prev = word.substring(0, i) + word.substring(i + 1);
                int prevLen = dp.getOrDefault(prev, 0) + 1;
                best = Math.max(best, prevLen);
            }
            dp.put(word, best);
            max = Math.max(max, best);
        }
        return max;
    }
     public static void main(String[] args) {
        String[] input = {"a", "at", "cat", "cart", "chart"};
        System.out.println(new LongestStringChain().longestStrChain(input)); // 5
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Edge Case: No related words? Each is a solo act. Max chain = 1.
• Letter Soup: Accidentally rearranging instead of inserting is a silent killer.
• Sort or be Sorry: If you don’t process words shortest to longest, your DP won’t have predecessors and you’ll stare at a wall of 1s.
• Performance: With N words of max L letters each, expect O(N * L²) time. Handle with care (or with a strong beverage).

🧠 Interviewer Brain-Tattoo

“Build your chains one block at a time — skyscrapers climb from the street, not the sky.”