#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

int longestAdjacentValidSubstring(const string& s, int k) {
    int n = s.length();
    if (n == 0) return 0;

    // dp[i] = largest valid substring ending at index "i"
    // Initialized to 1 because a single character is always a valid substring of length 1
    vector<int> dp(n, 1); 

    for (int i = 1; i < n; ++i) {
        // if(abs(s[i-1]-s[i])<=k)
        if (abs(s[i - 1] - s[i]) <= k) {
            // dp[i] = 1 + dp[i-1]
            dp[i] = 1 + dp[i - 1];
        } else {
            // dp[i] = 1
            dp[i] = 1;
        }
    }

    // -> Max(dp[1],dp[2],dp[3],................dp[n])
    // Note: C++ uses 0-based indexing, so this finds the max from dp[0] to dp[n-1]
    return *max_element(dp.begin(), dp.end());
}

int main() {
    // Example test cases
    string s1 = "abdfa";
    int k1 = 2;
    cout << "String: " << s1 << ", k = " << k1 << "\n";
    cout << "Max adjacent valid substring length: " << longestAdjacentValidSubstring(s1, k1) << "\n\n";

    string s2 = "adg";
    int k2 = 1;
    cout << "String: " << s2 << ", k = " << k2 << "\n";
    cout << "Max adjacent valid substring length: " << longestAdjacentValidSubstring(s2, k2) << "\n";

    return 0;
}