Tracxn (1+ Interviews) | Interview Experiences

Summary

This post details a specific coding question encountered during a Tracxn interview.

This post provides the full problem statement, input, output, and explanation for a coding question asked during a Tracxn interview round.

Find Valid Substrings Based on Character Frequency Constraints

Data Structures & Algorithms

You are given:

A string s of lowercase English letters.
An integer k, representing the required length of each substring.
A Map<Character, Integer> charCount, where each entry (ch, freq) specifies that character ch must appear at least freq times in a valid substring.

Your task:
Return a list of all unique substrings of length k from the string s such that:

Each character in charCount appears in the substring at least the number of times specified.
Substrings are considered unique, so repeated substrings should only appear once in the result.

without using substring and built in functions of string

Input:
s = "abacad"
k = 3
charCount = { 'a': 2, 'b': 1 }

Output:
["aba"]

Explanation:
- "aba" has two 'a's and one 'b'
- Other substrings of length 3: "bac", "aca", "cad" don't meet the character frequency criteria.