โจทย์
คืนค่าดัชนีของตัวอักษรตัวแรกใน text ที่ปรากฏเพียงครั้งเดียว (เปรียบเทียบตัวพิมพ์เล็ก-ใหญ่)
ให้เขียนฟังก์ชัน first_unique_index(text)
อินพุต
text: ข้อความที่ต้องการตรวจสอบ
เอาต์พุต
คืนค่าดัชนีของตัวอักษรที่พบ หรือ -1 หากไม่มีตัวอักษรใดที่ไม่ซ้ำเลย
เงื่อนไข
0 ≤ ความยาว ≤ 100,000
ตัวอย่าง
อินพุต:
text = "swiss"
ผลลัพธ์ที่คาดหวัง:
expected = 1
อินพุต:
std::string text = "swiss";
ผลลัพธ์ที่คาดหวัง:
long long expected = 1;
อินพุต:
string text = "swiss";
ผลลัพธ์ที่คาดหวัง:
long expected = 1;
คำอธิบาย
s ซ้ำ, w ปรากฏครั้งเดียวที่ดัชนี 1
อินพุต:
text = "aabb"
ผลลัพธ์ที่คาดหวัง:
expected = -1
อินพุต:
std::string text = "aabb";
ผลลัพธ์ที่คาดหวัง:
long long expected = -1;
อินพุต:
string text = "aabb";
ผลลัพธ์ที่คาดหวัง:
long expected = -1;
คำอธิบาย
ทุกตัวอักษรซ้ำหมด: -1
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
ต้องหาอักขระที่ปรากฏแค่ครั้งเดียว ไม่ใช่แค่ตัวที่ต่างตัวแรก
คำใบ้ 2
นับความถี่ของอักขระทั้งหมดก่อน แล้วค่อยหา index แรกที่มีความถี่เป็นหนึ่ง
คำใบ้ 3
อย่าลืมว่าอักษรตัวใหญ่กับตัวเล็กถือเป็นคนละอักขระ
ความซับซ้อนที่คาดหวัง
เวลา O(n), หน่วยความจำเพิ่ม O(k)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน