fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <cmath>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. int longestAdjacentValidSubstring(const string& s, int k) {
  10.     int n = s.length();
  11.     if (n == 0) return 0;
  12.  
  13.     // dp[i] = largest valid substring ending at index "i"
  14.     // Initialized to 1 because a single character is always a valid substring of length 1
  15.     vector<int> dp(n, 1); 
  16.  
  17.     for (int i = 1; i < n; ++i) {
  18.         // if(abs(s[i-1]-s[i])<=k)
  19.         if (abs(s[i - 1] - s[i]) <= k) {
  20.             // dp[i] = 1 + dp[i-1]
  21.             dp[i] = 1 + dp[i - 1];
  22.         } else {
  23.             // dp[i] = 1
  24.             dp[i] = 1;
  25.         }
  26.     }
  27.  
  28.     // -> Max(dp[1],dp[2],dp[3],................dp[n])
  29.     // Note: C++ uses 0-based indexing, so this finds the max from dp[0] to dp[n-1]
  30.     return *max_element(dp.begin(), dp.end());
  31. }
  32.  
  33. int main() {
  34.     // Example test cases
  35.     string s1 = "abdfa";
  36.     int k1 = 2;
  37.     cout << "String: " << s1 << ", k = " << k1 << "\n";
  38.     cout << "Max adjacent valid substring length: " << longestAdjacentValidSubstring(s1, k1) << "\n\n";
  39.  
  40.     string s2 = "adg";
  41.     int k2 = 1;
  42.     cout << "String: " << s2 << ", k = " << k2 << "\n";
  43.     cout << "Max adjacent valid substring length: " << longestAdjacentValidSubstring(s2, k2) << "\n";
  44.  
  45.     return 0;
  46. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
String: abdfa, k = 2
Max adjacent valid substring length: 4

String: adg, k = 1
Max adjacent valid substring length: 1
https://ideone.com/2RSrSl
dp paypal oa
language:
C++ (gcc 8.3)
created:
8 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!