Đếm cặp ký tự cùng khoảng cách như bảng chữ cái trong C++

Giới thiệu

Cho chuỗi ký tự, đếm số cặp (i, j) với i < j sao cho khoảng cách giữa hai ký tự trong chuỗi bằng khoảng cách trong bảng chữ cái: |str[i] - str[j]| == |i - j|.

Ví dụ

• "Tutorials Point" → 5 cặp: (u,t), (u,r), (t,r), (i,o), (s,n)
• "Learning is the best habit" → 12 cặp

Ý tưởng giải thuật

Duyệt tất cả cặp (i, j) với i < j (O(n²)), kiểm tra điều kiện abs(str[i] - str[j]) == abs(i - j).

Ví dụ triển khai (C++)

#include <bits/stdc++.h>
using namespace std;

int countAlphaDistancePairs(string str) {
    int count = 0;
    int len = str.length();
    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len; j++) {
            int charDist = abs(str[i] - str[j]);
            int posDist = abs(i - j);
            if (charDist == posDist)
                count++;
        }
    }
    return count;
}

int main() {
    string str = "Tutorials Point";
    cout << "So cap ky tu cung khoang cach: " << countAlphaDistancePairs(str); // 5
    return 0;
}

Đầu vào

"Tutorials Point"

Đầu ra

5