#include <iostream>
#include <string>
#include <set>
#include <algorithm>

using namespace std;

int longestValidSubstring(const string& s, int k) {
    int n = s.length();
    multiset<char> st;
    int i = 0;
    int j = 0;
    int maxLength = 0;

    while (j < n) {
        // Expand the window by adding the current character
        st.insert(s[j]);

        // Shrink the window from the left if the max difference exceeds k
        while (*st.rbegin() - *st.begin() > k) {
            st.erase(st.find(s[i]));
            ++i;
        }

        // Update the maximum length found so far
        maxLength = max(maxLength, j - i + 1);
        j++;
    }

    return maxLength;
}

int main() {
    // Example 1
    string s1 = "abdfa";
    int k1 = 2;
    cout << "String: " << s1 << ", k = " << k1 << "\n";
    cout << "Longest Valid Substring Length: " << longestValidSubstring(s1, k1) << "\n\n";
    // Explanation: "ab" (diff 1), "bd" (diff 2), "df" (diff 2) are valid. Max length is 2.

    // Example 2
    string s2 = "edcba";
    int k2 = 2;
    cout << "String: " << s2 << ", k = " << k2 << "\n";
    cout << "Longest Valid Substring Length: " << longestValidSubstring(s2, k2) << "\n";
    // Explanation: "edc" (diff 'e'-'c' = 2), "dcb" (diff 2), "cba" (diff 2). Max length is 3.

    return 0;
}