3597. Partition String

MediumTrieHash TableStringSimulation

Leetcode Link

Problem Description

Given a string s, partition it into unique segments according to the following procedure:

Start building a segment beginning at index 0.
Continue extending the current segment character by character until the current segment has not been seen before.
Once the segment is unique, add it to your list of segments, mark it as seen, and begin a new segment from the next index.
Repeat until you reach the end of s.

Return an array of strings segments, where segments[i] is the ith segment created.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

To solve this problem, notice that at each step, we want to create the longest possible segment that has not already appeared before. We can imagine keeping track of all the segments we have made so far in a set. As we read each character, we keep adding it to our current segment. As soon as this growing segment has not yet been made, we can finalize it, add it to our list, and start a new segment from the next character. This ensures every segment is unique and the process is greedy and straightforward: always make a new segment as soon as possible. Using a set helps us quickly check if a segment has already been used.

Solution Approach

We use a hash set vis to keep track of all unique segments we have already formed. This lets us check quickly whether our current segment has been seen before.

We iterate through the string s, building up a temporary string t character by character. For every character, we add it to t. Whenever t has not been seen in vis, we know it's a unique segment. At that point, we:

Add t to our result list
Mark t as seen by adding it to vis
Reset t to start forming a new segment from the next index

This process is repeated for each character in s until we've processed the entire string. By the end, our result list contains all the unique segments as required by the problem.

The approach uses a set for efficient lookups, and simulates the described segmentation process directly. The main operations—adding to the set, appending to a list, and resetting the temporary string—are all efficient.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use the string s = "abac" to walk through the solution approach.

Initialize:
- segments = []
- vis (set of seen segments) = {}
- t (current segment) = ""
Iterate through each character:
- i = 0, s[0] = 'a':
  - t = "a"
  - "a" not in vis → unique segment
  - Add "a" to segments → segments = ["a"]
  - Add "a" to vis → vis = {"a"}
  - Reset t = ""
- i = 1, s[1] = 'b':
  - t = "b"
  - "b" not in vis → unique segment
  - Add "b" to segments → segments = ["a", "b"]
  - Add "b" to vis → vis = {"a", "b"}
  - Reset t = ""
- i = 2, s[2] = 'a':
  - t = "a"
  - "a" already in vis, so continue
  - Next character: i = 3, s[3] = 'c':
    - t = "a" + "c" = "ac"
    - "ac" not in vis → unique segment
    - Add "ac" to segments → segments = ["a", "b", "ac"]
    - Add "ac" to vis → vis = {"a", "b", "ac"}
    - Reset t = ""
Result:
- The final list of unique segments is ["a", "b", "ac"].

This illustrates how the process extends the segment until it finds a new unique substring not seen earlier, then records that segment and restarts from the next character.

Solution Implementation

1from typing import List
2
3class Solution:
4    def partitionString(self, s: str) -> List[str]:
5        # Hash set to keep track of unique substrings already seen
6        seen = set()
7        # List to store the final partitions
8        partitions = []
9        # Temporary string to build the current substring
10        current = ""
11
12        for char in s:
13            current += char
14            # If the current substring has not been seen before
15            if current not in seen:
16                # Mark this substring as seen
17                seen.add(current)
18                # Add it to the result
19                partitions.append(current)
20                # Reset current for the next substring
21                current = ""
22
23        return partitions
24

1class Solution {
2    public List<String> partitionString(String s) {
3        Set<Character> seen = new HashSet<>();  // To track characters in the current partition
4        List<String> result = new ArrayList<>(); // To store the partitions
5        StringBuilder partition = new StringBuilder(); // To build the current substring
6
7        for (char currentChar : s.toCharArray()) {
8            // If character is already in the current partition, start a new partition
9            if (seen.contains(currentChar)) {
10                result.add(partition.toString()); // Add the current partition to the result
11                seen.clear();                     // Clear the set for the new partition
12                partition.setLength(0);           // Reset the StringBuilder
13            }
14            seen.add(currentChar);                // Add current character to set
15            partition.append(currentChar);        // Add character to current partition
16        }
17        // Add the last partition if any characters remain
18        if (partition.length() > 0) {
19            result.add(partition.toString());
20        }
21        return result;
22    }
23}
24

1class Solution {
2public:
3    vector<string> partitionString(string s) {
4        // To track unique substrings
5        unordered_set<string> seen;
6        vector<string> result;    // Stores the final partitioned substrings
7        string current = "";      // Temporarily holds the building substring
8
9        for (char ch : s) {
10            current += ch; // Add current character to substring
11
12            // If current substring not seen before, partition here
13            if (!seen.count(current)) {
14                seen.insert(current);     // Mark substring as seen
15                result.push_back(current);// Add to result
16                current = "";             // Start new substring
17            }
18        }
19        return result;
20    }
21};
22

1/**
2 * Splits the input string into substrings such that each substring has not appeared before.
3 * @param s The input string
4 * @returns An array of unique substrings
5 */
6function partitionString(s: string): string[] {
7    // Set to track unique substrings that have already been added
8    const seen = new Set<string>();
9    // Array to store the result substrings
10    const result: string[] = [];
11    // Temporary string to build the current substring
12    let current = '';
13
14    // Iterate through each character in the input string
15    for (const ch of s) {
16        current += ch;
17        // If the current substring hasn't been seen before
18        if (!seen.has(current)) {
19            seen.add(current);    // Mark as seen
20            result.push(current); // Add to the result array
21            current = '';         // Reset current substring builder
22        }
23    }
24    return result;
25}
26

Time and Space Complexity

The time complexity of the provided code is O(n^2), where n is the length of the string s. This is because, for each character, a new substring t is built and checked against the set vis, and the operation t not in vis can take up to O(n) time due to the string hashing and storage in Python sets. If substrings are longer, this check can approach O(n) per operation, leading to an overall O(n^2) complexity in the worst case.

The space complexity is O(n), as the set vis, the list ans, and the string t all together store up to n substrings or characters, each at most of size n.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

It's faster

It has better space complexity

Order of computer subproblems does not matter

It has better time complexity

I don't know