Partition String

Medium
1834.

Partition String

Partition String is a medium coding problem on strings, hash table and simulation, asked in Amazon interviews.

You are given a string s. Split it into segments with the following procedure:

  • Start a new segment at index 0 and keep a set of segments already produced (initially empty).
  • Extend the current segment one character at a time. As soon as it is a string not yet in the set, add it to the set and to the answer, and start a new segment at the next index.
  • If the string ends while the current segment is still one that was seen before, that leftover piece is discarded.

Return the segments in the order they were produced.

Example 1

Input
s = "aababa"
Output
["a","ab","aba"]
Explanation
`a` is new. Then `a` is seen, so it grows to `ab` (new). Then `a`, `ab` are seen, so it grows to `aba` (new).

Example 2

Input
s = "kairo"
Output
["k","a","i","r","o"]
Explanation
Every single letter is new.

Example 3

Input
s = "aaaa"
Output
["a","aa"]
Explanation
After `a` and `aa`, the last `a` is a segment already seen, so it is dropped.

Constraints

  • 1 <= s.length <= 10^5
  • s consists only of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {string[]}
 */
var partitionString = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Partition String — Solution in Python, Java & C++

Partition String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon.

Partition String is a medium coding problem on strings, hash table and simulation, asked in Amazon interviews.

  • Difficulty: Medium
  • Topics: Strings, Hash Table, Simulation, Trie
  • Asked at: Amazon
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a string s. Split it into segments with the following procedure:

  • Start a new segment at index 0 and keep a set of segments already produced (initially empty).
  • Extend the current segment one character at a time. As soon as it is a string not yet in the set, add it to the set and to the answer, and start a new segment at the next index.
  • If the string ends while the current segment is still one that was seen before, that leftover piece is discarded.

Return the segments in the order they were produced.

Example 1

Input: s = "aababa"
Output: ["a","ab","aba"]
Explanation: `a` is new. Then `a` is seen, so it grows to `ab` (new). Then `a`, `ab` are seen, so it grows to `aba` (new).

Example 2

Input: s = "kairo"
Output: ["k","a","i","r","o"]
Explanation: Every single letter is new.

Example 3

Input: s = "aaaa"
Output: ["a","aa"]
Explanation: After `a` and `aa`, the last `a` is a segment already seen, so it is dropped.

Constraints

  • 1 <= s.length <= 10^5
  • s consists only of lowercase English letters

Hints for Partition String

  1. Hint 1

    This is a direct simulation: build the current segment, test it against a hash set, and cut when it is new.

  2. Hint 2

    Notice that a segment only grows while it is already in the set — so every new segment is an earlier segment plus one character.

  3. Hint 3

    That means a trie works too: walk down from the root one character at a time, and the moment a child is missing, create it and cut. Each character then costs O(1).

How to solve Partition String

Simulate exactly as described. Because a segment only keeps growing while it is a previously produced segment, the produced segments form a trie (this is the LZ78 phrase parsing), so membership can be tested in constant time per character.

Approach

  1. Keep a set of produced segments (or a trie whose nodes are produced segments) and the current segment.
  2. For each character, append it to the current segment.
  3. If the extended segment is new, record it in the set and in the answer, and reset the current segment to empty.
  4. When the input ends, return the answer; an unfinished segment is ignored.

Why it works

The loop implements the definition step by step: a cut happens at the first extension that is not in the set, and that string is then added, so later segments are compared against everything produced before them. In the trie version, walking to an existing child means the extended string is a known segment, and a missing child means it is new.

Complexity

  • Time — O(n) with the trie; O(n * L) with a hash set of strings, L the longest segment (about sqrt(2n))
  • Space — O(n)

Pitfalls

  • Do not append the trailing leftover — it is a segment already seen.
  • Reset the segment after recording it, so the next segment starts at the following character.

Reference solution

Python

from typing import List

def partitionString(s: str) -> List[str]:
    seen = set()
    out = []
    start = 0
    for i in range(len(s)):
        seg = s[start:i + 1]
        if seg not in seen:
            seen.add(seg)
            out.append(seg)
            start = i + 1
    return out

Java

public static String[] partitionString(String s) {
    Set<String> seen = new HashSet<>();
    List<String> out = new ArrayList<>();
    int start = 0;
    for (int i = 0; i < s.length(); i++) {
        String seg = s.substring(start, i + 1);
        if (seen.add(seg)) {
            out.add(seg);
            start = i + 1;
        }
    }
    return out.toArray(new String[0]);
}

C++

vector<string> partitionString(string s) {
    unordered_set<string> seen;
    vector<string> out;
    string cur;
    for (char c : s) {
        cur += c;
        if (seen.insert(cur).second) {
            out.push_back(cur);
            cur.clear();
        }
    }
    return out;
}

JavaScript

var partitionString = function(s) {
    var seen = new Set();
    var out = [];
    var cur = "";
    for (var i = 0; i < s.length; i++) {
        cur += s[i];
        if (!seen.has(cur)) {
            seen.add(cur);
            out.push(cur);
            cur = "";
        }
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets