Cho một chuỗi ‘s’, nhiệm vụ là tìm ký tự duy nhất đầu tiên không lặp lại trong chuỗi ký tự đã cho và trả về chỉ mục của nó dưới dạng đầu ra. Nếu không có ký tự nào như vậy hiện diện trong chuỗi đã cho, chúng tôi sẽ trả về ‘-1’ dưới dạng đầu ra. Ví dụ,
Đầu vào-1 -
s = “tutorialspoint”
Đầu ra -
1
Giải thích - Trong chuỗi đã cho “tutorialspoint”, ký tự duy nhất đầu tiên không lặp lại là ‘u’ có chỉ số ‘1’. Do đó, chúng tôi sẽ trả về ‘1’ dưới dạng đầu ra.
Đầu vào-2 -
s = “aaasttarrs”
Đầu ra -
-1
Giải thích - Trong chuỗi đã cho “aaasttarrs”, không có ký tự duy nhất. Vì vậy, chúng tôi sẽ trả về đầu ra là ‘-1’.
Phương pháp được sử dụng để giải quyết vấn đề này
Để tìm chỉ mục của ký tự duy nhất đầu tiên có trong chuỗi đã cho, chúng ta có thể sử dụng hashmap . Ý tưởng là xem qua tất cả các ký tự của chuỗi và tạo một bản đồ băm với Khóa là ký tự và Giá trị là các lần xuất hiện của nó.
Trong khi duyệt qua từng ký tự của chuỗi, chúng tôi sẽ lưu trữ các lần xuất hiện của từng ký tự nếu nó xuất hiện. Sẽ mất O (n) thời gian tuyến tính để lưu trữ các lần xuất hiện của mỗi ký tự. Sau đó, chúng ta sẽ đi qua bản đồ băm và sẽ kiểm tra xem có ký tự nào có tần suất nhỏ hơn 2 hoặc bằng ‘1’ hay không. Và chúng tôi sẽ trả về chỉ mục của ký tự cụ thể đó.
-
Lấy một chuỗi ‘s’ làm Đầu vào.
-
Một hàm Integer uniqueChar (string str) nhận một chuỗi làm đầu vào và trả về chỉ số của ký tự duy nhất xuất hiện đầu tiên.
-
Lặp lại chuỗi và tạo một bản đồ băm của char và các lần xuất hiện của nó trong khi xem qua từng ký tự của chuỗi.
-
Nếu có một ký tự có tần suất nhỏ hơn 2 hoặc bằng 1, thì trả về chỉ số của ký tự cụ thể đó.
-
Nếu không có ký tự duy nhất nào hiện diện trong chuỗi, hãy trả về ‘-1’ dưới dạng Đầu ra.
Ví dụ
#include<bits/stdc++.h>
using namespace std;
int uniqueChar(string str){
int ans = -1;
unordered_map<char,int>mp;
for(int i=0;str[i]!='\0'){
mp[str[i]]++;
}
for(int i=0;i<s.size();i++){
for(auto it= mp.begin();it!=mp.end();it++){
if(it->first==str[i] && it->second==1){
ans= i;
}
}
}
return ans;
}
int main(){
string s= "tutorialspoint";
cout<<uniqueChar(s)<<endl;
return 0;
} Đầu ra
Chạy đoạn mã trên sẽ in ra kết quả là,
1
Giải thích - Chuỗi đầu vào ‘tutorialspoint’ chứa các ký tự duy nhất là ‘u’, ’r’, và ‘l’, và ký tự duy nhất đầu tiên ‘u’ có chỉ số ‘1’. Vì vậy, chúng tôi lấy ‘1’ làm đầu ra.