เราได้รับสตริงที่ประกอบด้วยตัวอักษร (,),{,},[,] เท่านั้น เป้าหมายคือหาความยาวสูงสุดของสตริงที่ทำให้สมดุล (balanced) ได้โดยการสลับตัวอักษรติดกัน หรือลบตัวอักษรออก เราทำได้โดยเปรียบเทียบตัวอักษรติดกัน หากเป็นคู่ตรงข้าม สามารถสลับได้ ( }{, )(, ][ สลับได้ แต่ {{, )), [[, }}, )), ]] สลับไม่ได้)
นอกจากนี้ หากตัวอักษรไม่มีคู่ให้จับคู่ ก็สามารถลบออกได้ (เช่น "{{}][", ตัว { แรกลบได้ สตริงสมดุลยาว 4)
อินพุต
str[] = "{{{}}{]]][()" length 12
เอาต์พุต
Maximum length of balances string: 8
คำอธิบาย − str[0] และ str[1] สลับไม่ได้ ลบ str[0] → "{{}}{]]][()" str[1] และ str[2] สลับไม่ได้ ลบ str[1] → "{}}{]]][()" {} สมดุล }{ สลับได้ ลบ 2 ตัว ]] สลับ ][ และ () สมดุล สตริงสุดท้าย {}{}[]() ความยาว 8
อินพุต
str[] = "(((((()" length 7
เอาต์พุต
str[] = "(((((()" length 7
คำอธิบาย − มีแค่ str[5] และ str[6] สมดุล ลบตัวอื่นหมด สตริงสุดท้าย () ความยาว 2
วิธีการที่ใช้ในโปรแกรมด้านล่าง
- อาเรย์ str[] เก็บสตริงต้นฉบับ Length เก็บความยาว
- ฟังก์ชัน maxBalancedStr(char str[], int len) คืนค่าความยาวสตริงสมดุลสูงสุด
- count เก็บความยาว เริ่มต้น 0
- ลูปผ่านสตริง ตรวจสอบตัวอักษรติดกันว่าสลับได้เพื่อสมดุล หรือสมดุลอยู่แล้ว เพิ่ม count 2
- ตรวจสอบคู่: (),)( และ {},}{ และ [],][ เพิ่ม i ด้วยเพื่อข้ามคู่ถัดไป
- คืนค่า count
ตัวอย่างโค้ด
#include <bits/stdc++.h>
using namespace std;
int maxBalancedStr(char str[20], int len) {
int count = 0;
for (int i = 0; i < len; i++) {
if ((str[i] == '(' && str[i+1] == ')') || (str[i] == ')' && str[i+1] == '(')) {
count += 2; ++i;
} else if ((str[i] == '{' && str[i+1] == '}') || (str[i] == '}' && str[i+1] == '{')) {
count += 2; ++i;
} else if ((str[i] == '[' && str[i+1] == ']') || (str[i] == ']' && str[i+1] == '[')) {
count += 2; ++i;
}
}
return count;
}
int main() {
char str[] = ")([]]((";
int length = 7;
cout << maxBalancedStr(str, length);
return 0;
}
ผลลัพธ์
4
