หา Substring ที่มี Power ตามที่กำหนดใน C++

ในปัญหานี้ เราได้รับสตริง str และจำนวนเต็ม pow งานของเราคือ การหา substring ที่มี power เท่ากับค่าที่กำหนด

เราต้องคืนค่า substring ที่ power ของมันเท่ากับ pow

Power ของสตริง คือ ผลรวมของ power ของตัวอักษรแต่ละตัว

Power ของตัวอักษร: a → 1, b → 2, c → 3, ...

ตัวอย่างเพื่อความเข้าใจ

Input : string = "programming" power = 49 
Output : 'pro'

คำอธิบาย

Power of 'pro': p=16, r=18, o=15
Total = 16 + 18 + 15 = 49

แนวทางแก้ปัญหา

วิธีง่ายคือใช้ Nested Loop วนหา substring ทุกตัวคำนวณ power แล้วเช็ค

วิธีที่มีประสิทธิภาพมากกว่า: ใช้ Map เก็บค่า power สะสม (Prefix Power) คำนวณ power สะสมจนถึงตำแหน่งปัจจุบัน แล้วเช็คว่าใน map มีค่า (currPower - targetPower) หรือไม่ หากมี แสดงว่า substring ระหว่างตำแหน่งนั้นถึงตำแหน่งปัจจุบันมี power ตรงตามที่ต้องการ

อัลกอริทึม

• ขั้นตอนที่ 1 − เดินผ่านสตริง หา power สะสม (currPower)
• ขั้นตอนที่ 2 − เช็คว่าค่า (currPower - pow) มีอยู่ใน map หรือไม่
  • ขั้นตอนที่ 2.1 − ถ้ามี ให้พิมพ์ substring นั้น
• ขั้นตอนที่ 3 − ใส่ค่า currPower ลงใน map
• ขั้นตอนที่ 4 − หากเดินครบทุกตัวอักษรแล้วไม่เจอ ให้พิมพ์ 'not possible'

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

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

void findSubStringWithPower(string str, int power) {
    int i;
    unordered_map<int, int> powerSS;
    int currPower = 0;
    int N = str.length();
    
    for (i = 0; i < N; i++) {
        currPower = currPower + (str[i] - 'a' + 1);
        
        if (currPower == power) {
            cout << "Substring : " << str.substr(0, i + 1) << " has power " << power;
            return;
        }
        
        if (powerSS.find(currPower - power) != powerSS.end()) {
            cout << "Substring from index " << str.substr(powerSS[currPower - power] + 1, i - powerSS[currPower - power]);
            cout << " has power " << power;
            return;
        }
        
        powerSS[currPower] = i;
    }
    
    cout << "No substring found!";
}

int main() {
    string str = "programming";
    int power = 49;
    findSubStringWithPower(str, power);
    return 0;
}

ผลลัพธ์

Substring : pro has power 49