LeetCode 1525: Number of Good Ways to Split a String Solution

Master LeetCode problem 1525 (Number of Good Ways to Split a String), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1525. Number of Good Ways to Split a String

Medium

Hash Table String Dynamic Programming Bit Manipulation

Problem Explanation

Explanation:

To solve this problem, we can iterate through the string s and keep track of the count of distinct characters in the prefix and suffix of the string. We can use two hash sets to store the distinct characters for the prefix and suffix. At each index i, we can calculate the number of distinct characters in the prefix up to i and the number of distinct characters in the suffix from i+1 to the end of the string. If the counts are equal, it forms a good split.

Algorithm:

Initialize a hash set for the prefix and suffix.
Iterate through the string s.
For each character at index i, add it to the suffix set.
Calculate the distinct characters in the prefix up to index i.
Check if the number of distinct characters in the prefix is equal to the number of distinct characters in the suffix.
If they are equal, increment the count of good splits.
Return the count of good splits.

Time Complexity:

The time complexity of this algorithm is O(n) where n is the length of the input string s.

Space Complexity:

The space complexity of this algorithm is O(n) to store the hash sets.

Solution Code

class Solution {
    public int numSplits(String s) {
        int goodSplits = 0;
        Set<Character> prefixSet = new HashSet<>();
        Set<Character> suffixSet = new HashSet<>();
        
        int[] prefixCount = new int[s.length()];
        int[] suffixCount = new int[s.length()];
        
        for (int i = 0; i < s.length(); i++) {
            suffixSet.add(s.charAt(i));
            suffixCount[i] = suffixSet.size();
        }
        
        for (int i = s.length() - 1; i > 0; i--) {
            prefixSet.add(s.charAt(i));
            prefixCount[i] = prefixSet.size();
            
            if (prefixCount[i] == suffixCount[i-1]) {
                goodSplits++;
            }
        }
        
        return goodSplits;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1525 (Number of Good Ways to Split a String)?

This page provides optimized solutions for LeetCode problem 1525 (Number of Good Ways to Split a String) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1525 (Number of Good Ways to Split a String)?

The time complexity for LeetCode 1525 (Number of Good Ways to Split a String) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1525 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1525 in Java, C++, or Python.

Back to LeetCode Solutions