Leet Code (2405. Amazon Spring '23 HF)

2405. Optimal partition of String

 

Given a string s, partition the string into one or more substrings such that the characters in each substring are unique. That is, no letter appears in a single substring more than once.

 

Return the minimum number of substrings in such a partition.

Note that each character should belong to exactly one substring in a partition.

 

Example 1:

Input: s = "abacaba"
Output: 4
Explanation:
Two possible partitions are ("a","ba","cab","a") and ("ab","a","ca","ba").
It can be shown that 4 is the minimum number of substrings needed.

 

Example 2:

Input: s = "ssssss"
Output: 6
Explanation:
The only valid partition is ("s","s","s","s","s","s").

 

Constraints:

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

class Solution {
    func partitionString(_ s: String) -> Int {
        var str = ""
        var c = 1

        for i in s {
            if str.contains(i) {
                c += 1
                str = String(i)
            } else {
                str += String(i)
            }
        }
        return c
    }
}

 

https://leetcode.com/problems/optimal-partition-of-string/description/?source=submission-ac