Amazon Coding Question – Solved

```
To tackle this problem, it’s important to carefully analyze the conditions defining a valid substring and then explore how to efficiently count all such substrings without brute force, which would be inefficient for large input sizes.

Step 1: Understand the problem and conditions
- The input is a string consisting of characters from 'a' to 'g', so only 7 possible distinct characters.
- A substring is a contiguous segment of the string.
- A substring is valid if, for every character in it, the count of that character is at most the number of distinct characters present in that substring.
- For example, if a substring contains 3 distinct characters, then each character in that substring must appear no more than 3 times.
- We need to count how many substrings satisfy this property.

Step 2: Clarify the constraints and properties
- Since only 7 characters exist, the maximum distinct characters in any substring is 7.
- Each substring’s validity depends on two factors:
1. How many distinct characters appear in the substring.
2. The count of each character in that substring.
- The substring must have for each character: count ≤ number_of_distinct_characters.

Step 3: Naive approach and its limitations
- A naive method would consider all O(n^2) substrings and count characters in each, then check the condition.
- This approach would be too slow for large strings since counting and checking each substring individually is expensive.
- Thus, we need a more optimal strategy.

Step 4: Consider a sliding window approach
- Since substrings are contiguous, a sliding window or two-pointer technique is often useful.
- Use two pointers (start and end) to represent a window (substring).
- Expand end to the right, maintain counts of characters within the window.
- For each expansion, check if the substring is valid.
- If it’s valid, record or count all valid substrings ending at 'end' and starting between 'start' and 'end'.
- If invalid, move 'start' forward to try to restore validity.
- This allows us to efficiently count all valid substrings in O(n) or O(n * alphabet_size) time.

Step 5: Data structures to maintain counts and distinct characters
- Maintain a frequency array or map for characters in the current window.
- Keep track of how many distinct characters are currently in the window.
- After adding or removing a character, update the frequency and distinct count accordingly.

Step 6: Efficient validity checking
- For the validity condition, we need to confirm that for each character, its count ≤ number_of_distinct_characters.
- The challenge is to check this condition quickly when expanding or shrinking the window.
- Instead of checking all characters every time, consider keeping track of the maximum character count in the current window.
- If max_count ≤ distinct_count, the window is valid; otherwise, it’s invalid.
- This reduces checks to just one comparison per step.

Step 7: Algorithm outline
- Initialize two pointers at the start of the string.
- Initialize counts and distinct character count.
- Initialize result (count of valid substrings) to 0.
- Expand the end pointer character by character:
- Update counts and distinct count.
- Update max_count if needed.
- While window invalid (max_count > distinct_count), move start forward to shrink window:
- Update counts, distinct count, and max_count accordingly.
- Once valid, add (end - start + 1) to result because all substrings ending at 'end' and starting anywhere between 'start' and 'end' are valid.

Step 8: Handling updates of max_count efficiently
- When shrinking the window, max_count may reduce, so maintain max_count carefully.
- One way is to track counts of counts (like how many characters have count x).
- Alternatively, since alphabet size is small (7), updating max_count by scanning frequency array after shrink operations is feasible.

Step 9: Edge cases and verification
- Verify with examples such as strings with repeated characters, strings with all distinct characters.
- Consider minimal cases like empty string or string with one character.
- Check that counting substrings correctly accounts for overlapping substrings.

Step 10: Summary and complexity
- The approach leverages sliding window and frequency tracking to achieve a near-linear solution.
- At most each character is visited twice (once when expanding end pointer, once when moving start).
- Character count updates and checks are efficient due to limited alphabet.
- This approach can handle large inputs efficiently compared to naive methods.

By carefully maintaining counts, distinct character information, and using sliding window techniques, we can count all valid substrings meeting the criteria in an efficient and scalable way.
```