This soluiton addresses the challenge of counting reversible substrings where the reversed version would create a numerically smaller value.

DP Strategy

The dynamic programming approach builds solutions incrementally by comparing substring pairs:

• For substrings of length 2, directly compare characters
• For longer substrings, use previously computed results when endpoints are equal
• The solution progresses from smaller to larger substring lengths

Recurrence Relation

dp[i][j] = {
  true,           if str[i] > str[j]
  false,          if str[i] < str[j]
  dp[i+1][j-1],   if str[i] == str[j]
}

Complexity Analysis

The optimized DP solution achieves O(n²) time complexity, significantly better than the brute-force O(n³) alternative.

Implementation

#include <vector>
#include <string>
using namespace std;

int countReversibleSubstrings(string num) {
    int n = num.length();
    vector<vector<bool>> memo(n, vector<bool>(n, false));
    
    for (int length = 2; length <= n; length++) {
        for (int start = 0; start + length <= n; start++) {
            int end = start + length - 1;
            if (num[start] > num[end]) {
                memo[start][end] = true;
            }
            else if (num[start] == num[end] && end - start >= 2) {
                memo[start][end] = memo[start+1][end-1];
            }
        }
    }
    
    int total = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (memo[i][j]) total++;
        }
    }
    return total;
}

Alternative Implementation

#include <iostream>
using namespace std;

int main() {
    string input;
    cin >> input;
    int size = input.size();
    bool dp[size][size] = {false};
    
    for (int l = 2; l <= size; l++) {
        for (int i = 0; i <= size - l; i++) {
            int j = i + l - 1;
            if (input[i] > input[j]) {
                dp[i][j] = true;
            }
            else if (input[i] == input[j] && l > 2) {
                dp[i][j] = dp[i+1][j-1];
            }
        }
    }
    
    int result = 0;
    for (int i = 0; i < size; i++) {
        for (int j = i + 1; j < size; j++) {
            result += dp[i][j];
        }
    }
    cout << result;
    return 0;
}