Unique Substrings in Wraparound String ใน C++ : นับ Substring ที่อยู่ใน Infinite Wraparound String

ให้ String s เป็น **Infinite Wraparound String** ของ Alphabet: "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd..."

ให้ String p หาจำนวน **Unique Non-empty Substrings** ของ p ที่ **ปรากฏใน s**

ตัวอย่าง

p = "zab"

Substrings ใน p: "z", "a", "b", "za", "ab", "zab" -> ทั้ง 6 ตัวอยู่ใน s (เพราะเป็น רצף Alphabet ต่อเนื่อง)

Output: 6

ข้อสังเกตสำคัญ (Key Insight)

Substring อยู่ใน Wraparound String **ก็ต่อเมื่อ** ตัวอักษรใน Substring **เรียงตามลำดับ Alphabet ต่อเนื่อง** (wrap z->a ได้)

เช่น: "abc", "zab", "xyzab" ✓ | "ac", "ba", "azy" ✗

อัลกอริทึม: DP บนตัวอักษรตัวสุดท้าย (DP on Last Character)

กำหนด dp[c] = **ความยาวสูงสุด** ของ Valid Substring ที่ **ลงท้ายด้วยตัวอักษร c**

• ถ้า p[i] ต่อจาก p[i-1] ได้ (diff == 1 หรือ -25) -> len++
• Else -> len = 1 (เริ่ม Substring ใหม่)
• dp[p[i]] = max(dp[p[i]], len)

คำตอบ = Sum(dp[c]) สำหรับ c = 'a'..'z' เพราะ Substring ที่ลงท้าย c และยาว L จะครอบคลุม Substrings ทั้งหมดที่ลงท้าย c ความยาว 1..L (Unique โดยอัตโนมัติ)

ตัวอย่างโค้ด C++

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

class Solution {
public:
    int findSubstringInWraproundString(string p) {
        vector<int> dp(26, 0); // dp['a'..'z']
        int len = 0;            // Current consecutive length

        for (int i = 0; i < p.size(); i++) {
            if (i > 0 && (p[i] - p[i-1] == 1 || p[i-1] - p[i] == 25)) {
                len++; // Consecutive (wrap z->a allowed)
            } else {
                len = 1; // Reset
            }
            dp[p[i] - 'a'] = max(dp[p[i] - 'a'], len);
        }

        int ret = 0;
        for (int i = 0; i < 26; i++) ret += dp[i];
        return ret;
    }
};

Input / Output

Input:  "zab"
Output: 6

ความซับซ้อน (Complexity)

• Time: O(N) — วนผ่าน String 1 รอบ
• Space: O(1) — Array 26 ตัว

ทำไม Sum(dp) ถูกต้อง?

ถ้า dp['c'] = 3 หมายถึงมี Valid Substring ลงท้าย 'c' ยาว 1,2,3 -> "c", "bc", "abc" ทั้ง 3 ตัว Unique และไม่ซ้ำกับ Substring ที่ลงท้ายตัวอื่นครับ