Setelah mempelajari beragam algoritma string matching, sekarang kita lihat pola soal klasik yang sering muncul di wawancara teknis, kompetisi pemrograman, dan aplikasi nyata. Empat pola yang akan kita bedah: palindrome check, anagram check, longest substring tanpa karakter berulang, dan longest palindromic substring. Masing-masing punya pendekatan brute force dan pendekatan optimal, sehingga kita bisa menghargai mengapa sliding window atau expand-around-center menang. Pada Chapter ini kita akan membandingkan kompleksitas tiap pendekatan dan mengimplementasikannya dalam C++.

Pola 1: Palindrome Check #

Aturan #

String S adalah palindrome bila S == S^R (reverse). Contoh: "katak", "racecar", "aba".

Mekanisme: Two-Pointer #

Gunakan dua pointer l dari awal dan r dari akhir. Bandingkan S[l] dengan S[r], lalu maju l dan mundur r. Bila ada mismatch → bukan palindrome. Kompleksitas O(n) waktu, O(1) ruang.

Kode #

cpp 
#include <iostream>
#include <string>

bool is_palindrome(const std::string& s) {
    int l = 0, r = static_cast<int>(s.size()) - 1;
    while (l < r) {
        if (s[l] != s[r]) return false;
        ++l; --r;
    }
    return true;
}

int main() {
    std::cout << "Palindrome:\n";
    std::cout << "  \"racecar\" : " << (is_palindrome("racecar") ? "ya" : "tidak") << '\n';
    std::cout << "  \"hello\"    : " << (is_palindrome("hello")    ? "ya" : "tidak") << '\n';
    std::cout << "  \"katak\"    : " << (is_palindrome("katak")    ? "ya" : "tidak") << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
Palindrome:
  "racecar" : ya
  "hello"    : tidak
  "katak"    : ya
  1. int l = 0, r = static_cast<int>(s.size()) - 1;: dua pointer dari ujung berlawanan.
  2. while (l < r): berhenti saat kedua pointer bertemu atau lewat — semua pasangan sudah diperiksa.
  3. if (s[l] != s[r]) return false;: mismatch awal → bukan palindrome.
  4. ++l; --r;: maju ke pasangan berikutnya.
  5. Hasil: "racecar" palindrome (r-a-c-e-c-a-r simetris); "hello" bukan (h ≠ o); "katak" palindrome.

Pola 2: Anagram Check #

Aturan #

Dua string A dan B adalah anagram bila bisa disusun ulang menjadi sama. Contoh: "listen" ↔ "silent", "makan" ↔ "nakam".

Mekanisme: Frequency Array #

Karena anagram hanya bergantung pada multiset karakter, hitung frekuensi tiap karakter di kedua string. Bila semua frekuensi sama → anagram.

Kode #

cpp 
#include <iostream>
#include <string>

bool is_anagram(const std::string& a, const std::string& b) {
    if (a.size() != b.size()) return false;
    int freq[26] = {0};
    for (char c : a) freq[c - 'a']++;
    for (char c : b) freq[c - 'a']--;
    for (int x : freq) if (x != 0) return false;
    return true;
}

int main() {
    std::cout << "Anagram:\n";
    std::cout << "  (\"listen\", \"silent\") : "
              << (is_anagram("listen", "silent") ? "ya" : "tidak") << '\n';
    std::cout << "  (\"hello\",  \"world\")   : "
              << (is_anagram("hello",  "world")   ? "ya" : "tidak") << '\n';
    std::cout << "  (\"makan\",  \"nakam\")   : "
              << (is_anagram("makan",  "nakam")   ? "ya" : "tidak") << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
Anagram:
  ("listen", "silent") : ya
  ("hello",  "world")   : tidak
  ("makan",  "nakam")   : ya
  1. if (a.size() != b.size()) return false;: anagram wajib sama panjang — cek awal menghemat kerja.
  2. int freq[26] = {0};: frequency array untuk alphabet a-z. Untuk Unicode atau ASCII 256, ganti dengan int freq[256] atau unordered_map<char, int>.
  3. for (char c : a) freq[c - 'a']++;: inkrementasi tiap karakter di a.
  4. for (char c : b) freq[c - 'a']--;: dekrementasi untuk b. Bila anagram, semua freq kembali 0.
  5. for (int x : freq) if (x != 0) return false;: cek akhir. Bila ada freq ≠ 0 → bukan anagram.
  6. Kompleksitas: O(n) waktu, O(1) ruang (array 26 konstan).

Pola 3: Longest Substring Tanpa Karakter Berulang #

Aturan #

Temukan panjang substring terpanjang di S tanpa karakter berulang. Contoh: "abcabcbb" → "abc" panjang 3. "pwwkew" → "wke" panjang 3.

Mekanisme: Sliding Window Variabel #

Gunakan dua pointer left dan right. Array last_pos[c] menyimpan posisi terakhir karakter c. Saat menemui karakter berulang, geser left ke last_pos[c] + 1. Window [left, right] selalu berisi substring tanpa duplikat.

Kode #

cpp 
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

int longest_unique_substring(const std::string& s) {
    std::vector<int> last_pos(256, -1);
    int best = 0, left = 0;
    for (int right = 0; right < static_cast<int>(s.size()); ++right) {
        char c = s[right];
        if (last_pos[(unsigned char)c] >= left) {
            left = last_pos[(unsigned char)c] + 1;
        }
        last_pos[(unsigned char)c] = right;
        best = std::max(best, right - left + 1);
    }
    return best;
}

int main() {
    std::cout << "Longest unique substring:\n";
    std::cout << "  \"abcabcbb\" : " << longest_unique_substring("abcabcbb") << '\n';
    std::cout << "  \"bbbbbb\"   : " << longest_unique_substring("bbbbbb") << '\n';
    std::cout << "  \"pwwkew\"   : " << longest_unique_substring("pwwkew") << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
Longest unique substring:
  "abcabcbb" : 3
  "bbbbbb"   : 1
  "pwwkew"   : 3
  1. std::vector<int> last_pos(256, -1);: posisi terakhir karakter. -1 = belum pernah muncul.
  2. if (last_pos[c] >= left): cek apakah karakter c muncul di dalam window saat ini ([left, right)). Bila ya → window baru harus mulai setelah kemunculan terakhir.
  3. left = last_pos[c] + 1;: geser left melompati karakter berulang. Tidak perlu mundur right — sliding window maju monoton.
  4. last_pos[c] = right;: update posisi terakhir.
  5. best = std::max(best, right - left + 1);: catat panjang window terbaik.
  6. Kompleksitas: O(n) waktu, O(1) ruang (alphabet 256). Jauh lebih baik dari brute force O(n³).

Pola 4: Longest Palindromic Substring #

Aturan #

Temukan substring terpanjang di S yang merupakan palindrome. Contoh: "babad" → "bab" (atau "aba"); "bananas" → "anana".

Mekanisme: Expand Around Center #

Untuk setiap posisi i di S, perluas ke kiri dan kanan selama karakter sama. Ada dua tipe center:

  • Ganjil (l = i, r = i): palindrome berpusat di satu karakter.
  • Genap (l = i, r = i + 1): palindrome berpusat di antara dua karakter.

Kompleksitas O(n²) waktu, O(1) ruang. Untuk O(n), gunakan algoritma Manacher.

Kode #

cpp 
#include <iostream>
#include <string>

std::string longest_palindromic_substr(const std::string& s) {
    int n = static_cast<int>(s.size());
    if (n == 0) return "";
    int best_start = 0, best_len = 1;

    auto expand = [&](int l, int r) {
        while (l >= 0 && r < n && s[l] == s[r]) { --l; ++r; }
        int len = r - l - 1;
        if (len > best_len) {
            best_len = len;
            best_start = l + 1;
        }
    };

    for (int i = 0; i < n; ++i) {
        expand(i, i);      // palindrome ganjil
        expand(i, i + 1);  // palindrome genap
    }
    return s.substr(best_start, best_len);
}

int main() {
    std::cout << "Longest palindromic substring:\n";
    std::cout << "  \"babad\"    : " << longest_palindromic_substr("babad") << '\n';
    std::cout << "  \"cbbd\"     : " << longest_palindromic_substr("cbbd") << '\n';
    std::cout << "  \"bananas\"  : " << longest_palindromic_substr("bananas") << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
Longest palindromic substring:
  "babad"    : bab
  "cbbd"     : bb
  "bananas"  : anana
  1. best_start = 0, best_len = 1;: inisialisasi — paling tidak, single karakter adalah palindrome.
  2. auto expand = [&](int l, int r) {...}: lambda. Perluas selama s[l] == s[r]. Setelah loop berhenti, valid window adalah [l+1, r-1].
  3. expand(i, i);: center ganjil — palindrome berpusat di karakter i. Contoh untuk "aba" di i = 1: l=r=1 cocok (b==b), l=0, r=2 cocok (a==a), l=-1, r=3 stop. Valid [0, 2] → “aba”.
  4. expand(i, i + 1);: center genap — palindrome berpusat di antara i dan i+1. Untuk "bb" di i = 0: l=0, r=1 cocok, l=-1, r=2 stop. Valid [0, 1] → “bb”.
  5. Hasil: "babad" → "bab" (atau "aba" — sama-sama panjang 3, tergantung urutan ekspansi). "cbbd" → "bb". "bananas" → "anana" (palindrome panjang 5).

Tabel Ringkasan Kompleksitas #

PolaBrute ForceOptimalRuang
Palindrome checkO(n)O(n)O(1)
Anagram checkO(n log n) (sort)O(n)O(1) (alphabet kecil)
Longest unique substringO(n³)O(n) sliding windowO(1)
Longest palindromic substringO(n³)O(n²) expand, O(n) ManacherO(1) atau O(n)

Pola Lain yang Umum #

1. Reverse String #

cpp 
std::reverse(s.begin(), s.end());  // STL

O(n) in-place.

2. String Compression (Run-Length) #

text 
"aaabbcccc" → "a3b2c4"

Iterasi, hitung run, bangun string hasil. O(n).

3. Count Vowels/Consonants #

Iterasi sekali, kategorikan per karakter. O(n).

4. String Rotation #

Cek apakah A adalah rotasi B: B.size() == A.size() && (A + A).find(B) != npos. O(n).

5. First Non-Repeating Character #

Hitung frequency sekali, lalu iterasi kedua untuk temukan karakter dengan freq = 1. O(n).

Aplikasi Nyata #

  • Spell checker: anagram dan edit distance (Chapter Edit Distance).
  • Autocomplete: trie + frequency (Chapter Trie).
  • Plagiarisme detector: rolling hash atau suffix array.
  • DNA motif finding: Aho-Corasick atau suffix array untuk banyak motif.
  • URL slug normalization: lowercase + filter non-alphanumeric.
  • Editor features: bracket matching, palindrome detection untuk auto-format.

Ringkasan #

  • Palindrome check: two-pointer O(n), ruang O(1).
  • Anagram check: frequency array O(n), ruang O(alphabet). Alternatif sort O(n log n).
  • Longest unique substring: sliding window variabel O(n) dengan last_pos array.
  • Longest palindromic substring: expand-around-center O(n²); Manacher O(n) untuk kasus ekstrem.
  • Pola umum lain: reverse, run-length compression, string rotation, first non-repeating.
  • Untuk wawancara, fokus pada pola sliding window dan expand-around-center — paling sering muncul dan relatif mudah.
  • Banyak masalah string lanjutan memerlukan struktur yang dipelajari di Chapter sebelumnya: trie, KMP, suffix array, rolling hash — pilih struktur sesuai karakteristik masalah.