island letter

import java.io.*;
import java.util.*;

class Result {

    /*
     * Complete the 'letterIslands' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts following parameters:
     *  1. STRING s
     *  2. INTEGER k
     */

    public static int letterIslands(String s, int k) {
        // This set will store all unique substrings that generate exactly k islands.
        Set<String> resultSet = new HashSet<>();
        
        // Length of the string
        int n = s.length();
        
        // Iterate over all possible starting positions of the substring
        for (int i = 0; i < n; i++) {
            StringBuilder currentSubstring = new StringBuilder();
            Set<Integer> markedPositions = new HashSet<>();
            
            // Iterate over all possible ending positions of the substring
            for (int j = i; j < n; j++) {
                // Append current character to the current substring
                currentSubstring.append(s.charAt(j));
                
                // Mark the current position
                for (int m = i; m <= j; m++) {
                    markedPositions.add(m);
                }
                
                // Now count the contiguous groups (islands)
                int islands = countIslands(markedPositions);
                
                // If the substring forms exactly k islands, add it to the set
                if (islands == k) {
                    resultSet.add(currentSubstring.toString());
                }
            }
        }
        
        // The result is the size of the set containing valid substrings
        return resultSet.size();
    }
    
    // Helper function to count the number of contiguous groups (islands)
    private static int countIslands(Set<Integer> markedPositions) {
        List<Integer> positions = new ArrayList<>(markedPositions);
        Collections.sort(positions);
        
        // Count the number of contiguous segments
        int islandCount = 1;
        for (int i = 1; i < positions.size(); i++) {
            if (positions.get(i) != positions.get(i - 1) + 1) {
                islandCount++;
            }
        }
        
        return islandCount;
    }
}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String s = bufferedReader.readLine();
        int k = Integer.parseInt(bufferedReader.readLine().trim());

        int result = Result.letterIslands(s, k);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedReader.close();
        bufferedWriter.close();
    }
}