[Swift] 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 <= $10^5$
• s consists of only English lowercase letters.

풀러가기

문제 이해

코드

func partitionString(_ s: String) -> Int {
  var result: [String] = [""]
  var index = 0
  for c in s {
    var current = result[index]
    if current.contains(c) {
      result.append("\(c)")
      index += 1
    } else {
      result[index] = current + "\(c)"
    }
  }
  return result.count
}

풀이

-

다른 분의 멋진 코드

• Time complexity: O(n)
• Space complexity: O(1)

func partitionString(_ s: String) -> Int {
  var map = Array(repeating: false, count: 26)
  var ans = 1
  for c in s
  {
    if map[Int(c.asciiValue! - 97)]
    {
      ans += 1
      map = Array(repeating: false, count: 26)
    }
    map[Int(c.asciiValue! - 97)] = true
  }
  return ans
}

Link

잘 배웠습니다.

-