Partition String

medium trie string simulation

Problem

Partition a string s into unique segments. Start a segment at index 0 and keep extending it character by character. The moment the current segment has not been seen before, add it to the answer, mark it as seen, and begin a fresh segment from the next index. Repeat until you reach the end of s, then return the list of segments.

Inputs = "abbccccd"

Output["a","b","bc","c","cc","d"]

"a", "b" are new. At index 2 "b" was already seen, so we extend to "bc" (new). Then "c" is new; at index 5 "c" repeats so we extend to "cc" (new); finally "d" is new.

s (lowercase letters)

def partitionString(s):
    seen = set()          # every segment already emitted
    segments = []         # the answer
    cur = ""              # segment being built
    for ch in s:
        cur += ch         # extend current segment
        if cur not in seen:
            segments.append(cur)   # it is unique -> emit it
            seen.add(cur)          # mark it seen
            cur = ""               # start a fresh segment
    return segments

function partitionString(s) {
  const seen = new Set();   // every segment already emitted
  const segments = [];      // the answer
  let cur = "";             // segment being built
  for (const ch of s) {
    cur += ch;              // extend current segment
    if (!seen.has(cur)) {
      segments.push(cur);   // it is unique -> emit it
      seen.add(cur);        // mark it seen
      cur = "";             // start a fresh segment
    }
  }
  return segments;
}

List<String> partitionString(String s) {
    Set<String> seen = new HashSet<>();   // segments already emitted
    List<String> segments = new ArrayList<>();
    StringBuilder cur = new StringBuilder();
    for (char ch : s.toCharArray()) {
        cur.append(ch);                   // extend current segment
        String seg = cur.toString();
        if (!seen.contains(seg)) {
            segments.add(seg);            // unique -> emit it
            seen.add(seg);                // mark it seen
            cur.setLength(0);             // start a fresh segment
        }
    }
    return segments;
}

vector<string> partitionString(string s) {
    unordered_set<string> seen;   // segments already emitted
    vector<string> segments;
    string cur = "";              // segment being built
    for (char ch : s) {
        cur += ch;                // extend current segment
        if (!seen.count(cur)) {
            segments.push_back(cur);  // unique -> emit it
            seen.insert(cur);         // mark it seen
            cur = "";                 // start a fresh segment
        }
    }
    return segments;
}

Explanation

This is a greedy simulation: we walk through s once, building one segment at a time and committing it the instant it becomes something we have never produced before.

We keep three things: cur, the characters accumulated for the segment we are currently forming; seen, the set of every segment already emitted; and segments, the answer. For each character we append it to cur and ask: is this exact string already in seen?

If cur is new, the greedy rule fires: we push cur into segments, record it in seen, and reset cur to empty so the next character starts a brand-new segment. If cur is already seen, we simply keep extending it with the next character — it must grow until it becomes unique.

The membership check is where a trie shines. Each emitted segment is a root-to-node path; testing whether cur is new means walking down from the root one character at a time, which is exactly what we are doing as we extend the segment. A hash set works too — both give the same answer — but the trie matches the incremental "add one character, check again" shape of the algorithm.

Example: s = "abbccccd". "a" and "b" are new singletons. At index 2 the next "b" alone was already emitted, so we extend to "bc", which is new. "c" is new; the second "c" repeats, so it grows to "cc"; finally "d" is new. The answer is ["a","b","bc","c","cc","d"].

Time: O(n · L) Space: O(total segment length)