Welcome to Subscribe On Youtube

3597. Partition String

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.

 

Example 1:

Input: s = "abbccccd"

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

Explanation:

Index Segment After Adding Seen Segments Current Segment Seen Before? New Segment Updated Seen Segments
0 "a" [] No "" ["a"]
1 "b" ["a"] No "" ["a", "b"]
2 "b" ["a", "b"] Yes "b" ["a", "b"]
3 "bc" ["a", "b"] No "" ["a", "b", "bc"]
4 "c" ["a", "b", "bc"] No "" ["a", "b", "bc", "c"]
5 "c" ["a", "b", "bc", "c"] Yes "c" ["a", "b", "bc", "c"]
6 "cc" ["a", "b", "bc", "c"] No "" ["a", "b", "bc", "c", "cc"]
7 "d" ["a", "b", "bc", "c", "cc"] No "" ["a", "b", "bc", "c", "cc", "d"]

Hence, the final output is ["a", "b", "bc", "c", "cc", "d"].

Example 2:

Input: s = "aaaa"

Output: ["a","aa"]

Explanation:

Index Segment After Adding Seen Segments Current Segment Seen Before? New Segment Updated Seen Segments
0 "a" [] No "" ["a"]
1 "a" ["a"] Yes "a" ["a"]
2 "aa" ["a"] No "" ["a", "aa"]
3 "a" ["a", "aa"] Yes "a" ["a", "aa"]

Hence, the final output is ["a", "aa"].

 

Constraints:

  • 1 <= s.length <= 105
  • s contains only lowercase English letters.

Solutions

Solution 1: Hash Table + Simulation

We can use a hash table $\textit{vis}$ to record the segments that have already appeared. Then, we traverse the string $s$, building the current segment $t$ character by character until this segment has not appeared before. Each time we construct a new segment, we add it to the result list and mark it as seen.

After the traversal, we simply return the result list.

The time complexity is $O(n \times \sqrt{n})$, and the space complexity is $O(n)$, where $n$ is the length of the string $s$.

  • class Solution {
    public List<String> partitionString(String s) {
        Set<String> vis = new HashSet<>();
        List<String> ans = new ArrayList<>();
        String t = "";
        for (char c : s.toCharArray()) {
            t += c;
            if (vis.add(t)) {
                ans.add(t);
                t = "";
            }
        }
        return ans;
    }
}

  • class Solution {
public:
    vector<string> partitionString(string s) {
        unordered_set<string> vis;
        vector<string> ans;
        string t = "";
        for (char c : s) {
            t += c;
            if (!vis.contains(t)) {
                vis.insert(t);
                ans.push_back(t);
                t = "";
            }
        }
        return ans;
    }
};

  • class Solution:
    def partitionString(self, s: str) -> List[str]:
        vis = set()
        ans = []
        t = ""
        for c in s:
            t += c
            if t not in vis:
                vis.add(t)
                ans.append(t)
                t = ""
        return ans


  • func partitionString(s string) (ans []string) {
	vis := make(map[string]bool)
	t := ""
	for _, c := range s {
		t += string(c)
		if !vis[t] {
			vis[t] = true
			ans = append(ans, t)
			t = ""
		}
	}
	return
}

  • function partitionString(s: string): string[] {
    const vis = new Set<string>();
    const ans: string[] = [];
    let t = '';
    for (const c of s) {
        t += c;
        if (!vis.has(t)) {
            vis.add(t);
            ans.push(t);
            t = '';
        }
    }
    return ans;
}

All Problems

All Solutions