Partition String - Practice Coding Problems

Partition String - Problem

You have a string s that you need to partition into unique segments using a greedy approach. The goal is to create the shortest possible segments while ensuring no two segments are identical.

Algorithm:

Start at index 0 and build a segment character by character
Keep extending the current segment until it becomes unique (not seen before)
Once unique, add it to your result and mark it as "seen"
Start a new segment from the next index
Repeat until the entire string is processed

Example: For string "abcabc", we get segments ["a", "b", "c", "ab", "c"] because when we reach the second 'a', we need "ab" to make it unique since "a" was already seen.

Input & Output

example_1.py — Basic Case

$ Input: s = "abcabc"

› Output: ["a", "b", "c", "ab", "c"]

💡 Note: Start with 'a' (unique) → 'b' (unique) → 'c' (unique) → second 'a' is seen, so extend to 'ab' (unique) → final 'c' is seen but we're at the end, so it becomes a separate segment

example_2.py — Repeated Pattern

$ Input: s = "aaaa"

› Output: ["a", "aa", "aaa"]

💡 Note: First 'a' is unique. Second 'a' is seen, but 'aa' is unique. Third 'a' is seen, 'aa' is seen, but 'aaa' is unique. Fourth 'a' continues the pattern.

example_3.py — All Unique Characters

$ Input: s = "abcdef"

› Output: ["a", "b", "c", "d", "e", "f"]

💡 Note: Each character is unique on its own, so each forms its own segment - this is the optimal greedy solution.

Constraints

1 ≤ s.length ≤ 1000
s consists of lowercase English letters only
The algorithm must use a greedy approach - always choose the shortest unique segment

Visualization

Tap to expand

Understanding the Visualization

Start Building

Begin with the first character and check if it's been seen before

Extend or Commit

If unique, save it as a segment. If seen, add another character

Track History

Use hash set to remember all previous segments

Repeat Process

Continue until the entire string is partitioned

Key Takeaway

🎯 Key Insight: By using a hash set to track seen segments and greedily choosing the shortest unique segment at each step, we can efficiently partition any string while maintaining uniqueness with optimal time complexity.

Asked in

G Google 15 a Amazon 12 f Meta 8 ⊞ Microsoft 6

The optimal solution uses a greedy approach with hash set for O(n²) time complexity. We iterate through the string once, building segments character by character. For each position, we extend the current segment and check if it exists in our hash set. As soon as we find a unique segment, we add it to both our result and hash set, then start building the next segment. This ensures we always get the shortest possible segments while maintaining uniqueness.

Common Approaches

Approach	Time	Space	Notes
✓ One-Pass Hash Set (Optimal)	O(n²)	O(n)	Use hash set to track seen segments while building partitions greedily
Brute Force (Generate All Partitions)	O(2^n)	O(n)	Generate all possible partitions and find the first valid one

One-Pass Hash Set (Optimal) — Algorithm Steps

Initialize a hash set to track seen segments and a result list
Start with an empty current segment at index 0
For each character, add it to the current segment
Check if current segment exists in the hash set
If not seen, add to result and hash set, reset current segment
If seen, continue building the segment
Return the list of segments

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with empty hash set and current segment

Build Segment

Add each character to current segment

Check Uniqueness

Look up current segment in hash set

Commit Segment

If unique, add to result and hash set, reset current

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_LEN 1000
#define MAX_SEGMENTS 100
#define HASH_SIZE 1009

typedef struct HashNode {
    char key[MAX_LEN];
    struct HashNode* next;
} HashNode;

HashNode* hashTable[HASH_SIZE];

unsigned int hash(const char* str) {
    unsigned int hash = 5381;
    for (int i = 0; str[i]; i++) {
        hash = ((hash << 5) + hash) + str[i];
    }
    return hash % HASH_SIZE;
}

int contains(const char* str) {
    unsigned int index = hash(str);
    HashNode* node = hashTable[index];
    while (node) {
        if (strcmp(node->key, str) == 0) return 1;
        node = node->next;
    }
    return 0;
}

void insert(const char* str) {
    if (contains(str)) return;
    unsigned int index = hash(str);
    HashNode* node = (HashNode*)malloc(sizeof(HashNode));
    strcpy(node->key, str);
    node->next = hashTable[index];
    hashTable[index] = node;
}

int main() {
    char s[MAX_LEN];
    fgets(s, MAX_LEN, stdin);
    s[strcspn(s, "\n")] = 0;
    
    // Remove quotes
    char* clean = s;
    if (s[0] == '"') clean++;
    int len = strlen(clean);
    if (clean[len-1] == '"') clean[len-1] = '\0', len--;
    
    char result[MAX_SEGMENTS][MAX_LEN];
    int count = 0;
    char current[MAX_LEN] = "";
    
    for (int i = 0; i < len; i++) {
        strncat(current, &clean[i], 1);
        if (!contains(current)) {
            insert(current);
            strcpy(result[count++], current);
            current[0] = '\0';
        }
    }
    
    printf("[");
    for (int i = 0; i < count; i++) {
        printf("\"%s\"", result[i]);
        if (i < count - 1) printf(", ");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

We visit each character once O(n), but string operations and hashing can take O(n) in worst case, giving O(n²) overall

⚠ Quadratic Growth

Space Complexity

O(n)

Hash set stores at most O(n) unique segments, each taking O(n) space in worst case

⚡ Linearithmic Space

24.5K Views

Medium Frequency

~12 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

One-Pass Hash Set (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler