10.22 Insert Stars

10.22.1 Problem Metadata

• Platform: Firecode.io
• Problem ID: Insert Stars
• Difficulty: Level 2
• URL: https://www.firecode.io/
• Tags:
• Techniques: Recursion, String

10.22.2 Description

Given a string s, recursively build a new string where any pair of identical adjacent characters is separated by a '*'.

10.22.3 Examples

Input: "cc"
Output: "c*c"

Input: "cac"
Output: "cac"

10.22.4 Constraints

• 1 <= s.length <= 10^4
• Characters are ASCII

10.22.5 Solution - Recursive Pair Expansion

10.22.5.1 Walkthrough

Base case is a single character. For longer strings, compare the first two characters. If equal, return first + "*" + recurse(s[1:]); otherwise, return first + recurse(s[1:]).

10.22.5.2 Analysis

• Time Complexity: O(n)
• Space Complexity: O(n) recursion depth

10.22.5.3 Implementation Steps

1. If s.length() <= 1, return s.
2. Recursively compute the transformed suffix rest = insertPairStar(s.substring(1)).
3. If s.charAt(0) == s.charAt(1), return s[0] + "*" + rest; else return s[0] + rest.

10.22.5.4 Code - Java

public String insertPairStar(String s) {
    if (s == null || s.length() <= 1) {
        return s;
    }
    String rest = insertPairStar(s.substring(1));
    if (s.charAt(0) == s.charAt(1)) {
        return s.charAt(0) + "*" + rest;
    }
    return s.charAt(0) + rest;
}