สตริงย่อยสุดท้ายในลำดับเล็กซิโครกราฟิกใน C++

ให้สตริง s หาสตริงย่อย (substring) ตัวสุดท้ายในลำดับเล็กซิโครกราฟิก (lexicographical order)

เช่น "abbbcabbc" เอาต์พุต = "cabbc"

วิธีแก้ − ใช้ Two Pointers (i, j, k) เปรียบเทียบสตริงย่อยเริ่มที่ i และ j ขยับ k เมื่อตัวอักษรเท่ากัน

ตัวอย่าง

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

class Solution { 
public: 
    string lastSubstring(string s) { 
        int i = 0, j = 1, k = 0; 
        while(j + k < s.size()){ 
            if(s[i+k] == s[j+k]) { k++; continue; } 
            if(s[i+k] < s[j+k]){ i = j; j++; } else { j = j + k + 1; } 
            k = 0; 
        } 
        return s.substr(i, s.size() - i); 
    } 
}; 

main(){ Solution ob; cout << (ob.lastSubstring("abbbcabbc")); }

อินพุต

"abbbcabbc"

เอาต์พุต

cabbc