The O(n) Club: Repeated Substring Pattern—Now With 100% More Magic Rope

The O(n) Club: Repeated Substring Pattern—Now With 100% More Magic Rope

⚡ TL;DR

Want to know if your string is secretly “la la la” caught in a loop? Double the string, chop off the first and last characters, and see if the original pops up inside. Java brute force works, but Houdini would use this trick:

// The string-doubling magic move
public boolean repeatedSubstringPattern(String s) {
    String dummy = s + s;
    return dummy.substring(1, dummy.length() - 1).contains(s);
}

🧠 How Devs Usually Mess This Up

Plenty of devs roll up their sleeves to brute force every possible substring—like trying every key on a keychain to unlock a door that was never locked. Many forget you can only subdivide by lengths that divide the string evenly, so they wind up building Frankenstrings that never match. Most wild of all: staring at those pesky substring indexes (the whole [1:-1] business) like they’re some ancient runic prophecy. It’s not magic; just off-by-one prevention!

🔍 What’s Actually Going On

Picture your string s like a silk rope tied in a loop. If it’s made of repeats, tying it to itself and snipping off the knots at both ends lets you find the exact original somewhere in the middle! Why? Because the copies must overlap perfectly—unless your string is a solo act. If the original only appears whole at the bookends, it’s a one-off string. If it pops up in the middle, congrats! Your string is about as original as a top-40 radio hook.

🛠️ PseudoCode

• Double the string: s + s
• Trim both ends: substring(1, 2*s.length() - 1)
• Check if the original sneaks in: window.contains(s)
• // If yes, the original’s a repeat pattern. If not, it’s one-of-a-kind.
• Java sample:

  String doubled = s + s;
  String window = doubled.substring(1, doubled.length() - 1);
  boolean isRepeat = window.contains(s);

• This shortcut beats brute-forcing, especially if you ever want your test cases to finish before lunch.

💻 The Code

// Java—fast and Houdini-approved
public class Solution {
    public boolean repeatedSubstringPattern(String s) {
        String doubled = s + s;
        String check = doubled.substring(1, doubled.length() - 1);
        return check.contains(s);
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Edge cases: Empty or 1-char strings are not your friends—skip these by default; they don’t repeat.
• CPU bonfires: Brute-force substring matching on big strings makes your computer cry for mercy.
• Time/space: Usually O(n), but for pathological, super-repetitive strings, Java’s contains could hiccup up to O(n^2). This is where you casually mention KMP… then don’t implement it.

🧠 Interviewer Brain-Tattoo

Why loop through slices when you can Houdini a string with s + s? If your code takes longer than the chorus of “Never Gonna Give You Up,” you’re doing it wrong.