# Solving Leetcode Interviews in Seconds with AI: Optimal Partition of String


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "2405" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

	# Problem Statement
	> 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.  

	# Explanation
	Here's a solution to the problem, along with explanations:

*   **Greedy Approach:** Iterate through the string, building substrings. If we encounter a character already in the current substring, we end the current substring and start a new one.

*   **Set for Uniqueness:** Use a set to efficiently track the characters present in the current substring.

*   **Minimum Substrings:** The greedy approach ensures we create a new substring only when absolutely necessary, minimizing the total count.

*   **Runtime and Storage Complexity:** O(n) runtime, O(1) storage, where n is the length of the string s. The set can contain at most 26 lowercase English letters, making its space usage constant.

	
	# Code
	```python
	def partitionString(s: str) -> int:
    """
    Partitions a string into substrings with unique characters and returns the minimum number of substrings.

    Args:
        s: The input string.

    Returns:
        The minimum number of substrings in the partition.
    """

    count = 1
    current_substring = set()

    for char in s:
        if char in current_substring:
            count += 1
            current_substring = set()
        current_substring.add(char)

    return count
	```