Substring Size K

Problem:

Given a string s and an int k, return all unique substrings of s of size k with k distinct characters.

Example 1:

Input: s = "abcabc", k = 3
Output: ["abc", "bca", "cab"]

Example 2:

Input: s = "abacab", k = 3
Output: ["bac", "cab"]

Example 3:

Input: s = "awaglknagawunagwkwagl", k = 4
Output: ["wagl", "aglk", "glkn", "lkna", "knag", "gawu", "awun", "wuna", "unag", "nagw", "agwk", "kwag"]
Explanation: 
Substrings in order are: "wagl", "aglk", "glkn", "lkna", "knag", "gawu", "awun", "wuna", "unag", "nagw", "agwk", "kwag", "wagl" 
"wagl" is repeated twice, but is included in the output once.

Constraints:

  • The input string consists of only lowercase English letters [a-z]
  • 0 ≤ k ≤ 26

Solution:

Logic:

import java.util.HashSet;
import java.util.Set;

public class SusbstringSizeK {

    public static void printUniqueSubstrings(String s, int k) {

        if (k <= s.length()) {
            Set<Character> uniqueCharacters = new HashSet<>();
            Set<String> uniqueSubstrings = new HashSet<>();
            for (int i = 0; i <= s.length() - k; i++) {
                String shorterString = s.substring(i, i + k);
                for (int j = 0; j < k; j++) {
                    uniqueCharacters.add(shorterString.charAt(j));
                }
                if (uniqueCharacters.size() == k) {
                    uniqueSubstrings.add(shorterString);
                }
                uniqueCharacters.clear();
            }
            uniqueSubstrings.stream().forEach(value -> System.out.println(value));
        }
    }

    public static void main(String[] args) {
        printUniqueSubstrings("abcabc", 3);
        printUniqueSubstrings("awaglknagawunagwkwagl", 4);
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s