Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2405.html

2405. Optimal Partition of String

  • Difficulty: Medium.
  • Related Topics: .
  • Similar Questions: Longest Substring Without Repeating Characters, Longest Substring with At Least K Repeating Characters, Partition Labels, Partition Array into Disjoint Intervals.

Problem

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.

Solution (Java, C++, Python)

  • class Solution {
        public int partitionString(String s) {
            int count = (s.isEmpty()) ? 0 : 1;
            HashSet<Character> letters = new HashSet<Character>(); // creating a set to find unique letters in substring
            for (int i = 0; i < s.length(); i++) {
                if (letters.contains(s.charAt(i))) { // if we encounter a duplicate
                    letters.clear(); // remove all letters in set
                    count++; // increment count
                }
                letters.add(s.charAt(i)); 
            }
            return count;
        }
    }
    
    ############
    
    class Solution {
        public int partitionString(String s) {
            int v = 0;
            int ans = 1;
            for (char c : s.toCharArray()) {
                int i = c - 'a';
                if (((v >> i) & 1) == 1) {
                    v = 0;
                    ++ans;
                }
                v |= 1 << i;
            }
            return ans;
        }
    }
    
  • class Solution:
        def partitionString(self, s: str) -> int:
            ans, v = 1, 0
            for c in s:
                i = ord(c) - ord('a')
                if (v >> i) & 1:
                    v = 0
                    ans += 1
                v |= 1 << i
            return ans
    
    ############
    
    # 2405. Optimal Partition of String
    # https://leetcode.com/problems/optimal-partition-of-string/
    
    class Solution:
        def partitionString(self, s: str) -> int:
            n = len(s)
            res = 1
            seen = set()
            
            for j, x in enumerate(s):
                if x in seen:
                    seen.clear()
                    res += 1
                    
                seen.add(x)
            
            return res
    
    
  • class Solution {
    public:
        int partitionString(string s) {
            int ans = 1;
            int v = 0;
            for (char c : s) {
                int i = c - 'a';
                if ((v >> i) & 1) {
                    v = 0;
                    ++ans;
                }
                v |= 1 << i;
            }
            return ans;
        }
    };
    
  • func partitionString(s string) int {
    	ans, v := 1, 0
    	for _, c := range s {
    		i := int(c - 'a')
    		if v>>i&1 == 1 {
    			v = 0
    			ans++
    		}
    		v |= 1 << i
    	}
    	return ans
    }
    
  • function partitionString(s: string): number {
        const set = new Set();
        let res = 1;
        for (const c of s) {
            if (set.has(c)) {
                res++;
                set.clear();
            }
            set.add(c);
        }
        return res;
    }
    
    
  • use std::collections::HashSet;
    impl Solution {
        pub fn partition_string(s: String) -> i32 {
            let mut set = HashSet::new();
            let mut res = 1;
            for c in s.as_bytes().iter() {
                if set.contains(c) {
                    res += 1;
                    set.clear();
                }
                set.insert(c);
            }
            res
        }
    }
    
    

Explain:

nope.

Complexity:

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

All Problems

All Solutions