Shortest Way to Form String ใน C++

ปัญหา

ให้ String Source และ Target หาจำนวน Subsequence ของ Source น้อยที่สุด ที่ต่อกันได้ Target ไม่ได้ → -1

Subsequence = ลบบางตัวอักษรออก คงลำดับ

ตัวอย่าง

Source="abc", Target="abcbc" → 2 (abc + bc)

อัลกอริทึม: Greedy + Binary Search

1. Preprocess: เก็บ Index ของแต่ละ Char ใน Source (Map<Char, Vector<Index>>)
2. เดิน Target ทีละตัว หา Index ใน Source ที่ > Previous Index (Upper Bound)
3. ไม่เจอ → เริ่ม Subsequence ใหม่ (Count++, Reset Index)

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

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

class Solution {
public:
    bool possible(string s, string t) {
        vector<bool> has(26, false);
        for (char c : s) has[c-'a'] = true;
        for (char c : t) if (!has[c-'a']) return false;
        return true;
    }
    
    int shortestWay(string s, string t) {
        if (!possible(s, t)) return -1;
        
        // Map char -> sorted indices
        vector<vector<int>> pos(26);
        for (int i = 0; i < s.size(); i++)
            pos[s[i]-'a'].push_back(i);
        
        int count = 1, prev = -1;
        
        for (char c : t) {
            auto& v = pos[c-'a'];
            // หา index แรกที่ > prev
            auto it = upper_bound(v.begin(), v.end(), prev);
            
            if (it == v.end()) {
                // เริ่ม subsequence ใหม่
                count++;
                prev = v[0];
            } else {
                prev = *it;
            }
        }
        return count;
    }
};

int main() {
    Solution ob;
    cout << ob.shortestWay("abc", "abcbc") << endl;  // 2
    cout << ob.shortestWay("abc", "acdbc") << endl;  // -1 (d ไม่อยู่ใน source)
    return 0;
}

ผลลัพธ์

2
-1

Complexity

• Time: O(|S| + |T| log |S|)
• Space: O(|S|)