Count With K Different Characters in Java
Count With K Different Characters explores the importance of using different characters in numerical representation, from digits in everyday arithmetic to unique symbols in fields like mathematics, linguistics, and computing. The concept of "K different characters" transcends notation and encompasses the nature of number systems and mathematical structures. The following article aims to unravel the hidden meanings and untold stories behind characters, illuminating the rich tapestry of human thought and creativity woven into numerical notation.
Example:
Input: str = “qffds”, k = 4
Output: 1
Explanation: There is only one substring, "qffds," with exactly 4 distinct characters for the input string "qffds" and k = 4. As a result, the output is 1, meaning that the condition is satisfied by a single substring.
Using the Sliding Window Approach
Algorithm
Step 1: Initialize the counter variable 'count' to 0.
Step 2: Store the input string's str' length in 'n'.
Step 3: Create an empty HashSet'set' for distinct characters.
Step 4: Iterate through each character in the string from index 0 to n-1.
Step 5: Initialize'set' as an empty HashSet for each character.
Step 6: Start another loop from the current index to the string end.
Step 7: Add each character of the substring to'set'.
Step 8: If'set' size equals 'k', increment 'count' by 1 and break out of the inner loop.
Step 9: Repeat steps 5-9 for each character.
Step10: Return 'count', representing a number of substrings with 'k' distinct characters.
Here is an implementation to count with k different characters using the sliding window approach :
FileName:SubstringsWithKDistinctCharacters.java
import java.util.HashSet; public class SubstringsWithKDistinctCharacters { // Method to count the number of substrings with exactly k distinct characters public static int countSubstringsWithKDistinctChars(String str, int k) { int count = 0; int n = str.length(); // HashSet to store distinct characters in a substring HashSetset; for (int i = 0; i < n; i++) { set = new HashSet<>(); // Loop through the string starting from index i for (int j = i; j < n; j++) { // Add characters to the set set.add(str.charAt(j)); // If the size of the set equals k, increment count if (set.size() == k) { count++; // If the size of the set exceeds k, break the loop, as it's not possible to have more than k distinct characters } else if (set.size() > k) { break; } } } return count; } public static void main(String[] args) { String str = "qffds"; int k = 4; System.out.println(countSubstringsWithKDistinctChars(str, k)); } }
Output:
1
Complexity analysis: The time complexity of the above method is O(n^2), where n is the input string'str' length. It is due to the fact that the string is iterated over by two nested loops, which produce a quadratic time complexity, and O(n), where n is the input string'str' length, is the space complexity. It is due to the fact that the input string's HashSet ' set' may store up to 'n' different characters.
Using HashMap
Algorithm
Step 1: Initialize the count variable to 0.
Step 2: Determine the input string length.
Step 3: Loop over each character in the string.
Step 4: Initialize HashMap for character and frequency storage.
Step 5: Start another loop from the current index to the string end.
Step 6: Update the frequency of each character.
Step 7: Increase the count variable if the HashMap size equals k.
Step 8: Break out of the inner loop if size exceeds k.
Step 9: Continue until all substrings are explored.
Step 10: Return count variable representing a number of substrings with k distinct characters.
Here is an implementation to count with k different characters using hashmap :
Filename: SubstringsWithKDistinctCharacters1.java
import java.util.HashMap; public class SubstringsWithKDistinctCharacters1 { // Method to count substrings with k distinct characters public static int countSubstringsWithKDistinctChars(String str, int k) { int count = 0; int n = str.length(); for (int i = 0; i < n; i++) { // Map to store the frequency of characters in the current substring HashMapmap = new HashMap<>(); for (int j = i; j < n; j++) { char c = str.charAt(j); // Current character map.put(c, map.getOrDefault(c, 0) + 1); // Update frequency of character // If the number of distinct characters in the current substring equals k, // increment count of substrings if (map.size() == k) { count++; } // If the number of distinct characters exceeds k, break the loop else if (map.size() > k) { break; } } } return count; // Return the count of substrings with k distinct characters } public static void main(String[] args) { String str = "qffds"; int k = 4; System.out.println(countSubstringsWithKDistinctChars(str, k)); } }
Output:
1
Complexity analysis: The time complexity of the above approach is O(n^2), where n is the input string'str' length. That's due to the fact that two nested loops iterate over the string, which has a potential inner loop traversal of up to 'n' characters for each character, and the space complexity is O(n), where n is the length of the input string'str'. It is due to the possibility that, in the worst case, the HashMap'map' could store up to 'n' distinct characters, each with a corresponding count.