Cara Menemukan Karakter yang Paling Sering Muncul dalam sebuah String

String adalah topik yang sangat penting dalam wawancara pemrograman. Adalah bijaksana untuk mempraktikkan beberapa masalah pemrograman yang berfokus pada string sebelum wawancara Anda. Dalam artikel ini, Anda akan mempelajari cara menemukan karakter yang paling sering muncul dalam sebuah string.

Contoh untuk Memahami Masalah

Contoh 1: Biarkan string yang diberikan menjadi "Makeuseof". Karakter 'e' muncul 2 kali dalam string yang diberikan dan semua karakter lainnya hanya muncul sekali. Dengan demikian, karakter 'e' memiliki frekuensi tertinggi dalam string yang diberikan.

Contoh 2: Biarkan string yang diberikan menjadi "Dia melihat keju". Karakter 'e' muncul 6 kali dalam string yang diberikan dan semua karakter lainnya muncul kurang dari 6 kali. Dengan demikian, karakter 'e' memiliki frekuensi tertinggi dalam string yang diberikan.

Pendekatan untuk Menemukan Karakter yang Paling Sering Muncul dalam sebuah String

Teknik hashing adalah cara paling efisien untuk menemukan karakter yang memiliki frekuensi tertinggi dalam sebuah string. Dalam teknik ini, string dilintasi dan setiap karakter string di-hash ke dalam array karakter ASCII.

Biarkan string input menjadi "Makeuseof", setiap karakter string ini di-hash sebagai berikut:

frekuensi['M'] = 1

frekuensi['a] = 1

frekuensi['k'] = 1

frekuensi['e'] = 2

frekuensi['u'] = 1

frekuensi['s'] = 1

frekuensi['o'] = 1

frekuensi['f'] = 1

Indeks nilai maksimum dalam larik frekuensi dikembalikan. Sini 2 adalah nilai tertinggi, oleh karena itu 'e' dikembalikan.

Program C++ untuk Menemukan Karakter Dengan Frekuensi Tertinggi

Di bawah ini adalah program C++ untuk mencari karakter dengan frekuensi tertinggi dalam sebuah string:

Terkait: Cara Menghitung Kemunculan Karakter yang Diberikan dalam sebuah String

// Program C++ untuk menemukan karakter
// memiliki frekuensi tertinggi dalam sebuah string
#sertakan 
#sertakan 
#tentukan ASCII_SIZE 256
menggunakan namespace std;
char maxFrequencyChar (string str)
{
// Array untuk menyimpan frekuensi setiap karakter
// Menginisialisasi frekuensi setiap karakter sebagai 0
int frekuensi[ASCII_SIZE] = {0};
// Menemukan panjang string input
int lenOfStr = str.panjang();
// Inisialisasi variabel maxFrequency
int maxFrequency = -1;
// Inisialisasi variabel maxFrequencyChar
char maxFrequencyChar;
// Melintasi dan memelihara
// frekuensi setiap karakter
untuk (int i = 0; saya < lenOfStr; saya++)
{
frekuensi[str[i]]++;
if (maxFrequency < frekuensi[str[i]])
{
maxFrequency = frekuensi[str[i]];
maxFrequencyChar = str[i];
}
}
kembali maxFrequencyChar;
}
// Kode Pengemudi
int utama()
{
string str1 = "Penyihir yang mana?";
cout<cout << "Karakter frekuensi tertinggi adalah: " << maxFrequencyChar (str1) << endl;
string str2 = "Dia melempar tiga lemparan bebas";
cout<cout << "Karakter frekuensi tertinggi adalah: " << maxFrequencyChar (str2) << endl;
string str3 = "Eddie mengeditnya";
cout<cout << "Karakter frekuensi tertinggi adalah: " << maxFrequencyChar (str3) << endl;
string str4 = "Penggunaan";
cout<cout << "Karakter frekuensi tertinggi adalah: " << maxFrequencyChar (str4) << endl;
string str5 = "Dia melihat keju";
cout<cout << "Karakter frekuensi tertinggi adalah: " << maxFrequencyChar (str5) << endl;
}

Keluaran:

str1: Penyihir yang mana?
Karakter frekuensi tertinggi adalah: h
str2: Dia melempar tiga lemparan bebas
Karakter frekuensi tertinggi adalah: e
str3: Eddie mengeditnya
Karakter frekuensi tertinggi adalah: d
str4: Makeuseof
Karakter frekuensi tertinggi adalah: e
str5: Dia melihat keju
Karakter frekuensi tertinggi adalah: e

Program Python untuk Menemukan Karakter Dengan Frekuensi Tertinggi

Di bawah ini adalah program Python untuk menemukan karakter dengan frekuensi tertinggi dalam sebuah string:

Terkait: Cara Membalikkan String di C++, Python, dan JavaScript

# Program Python untuk menemukan karakter
# memiliki frekuensi tertinggi dalam sebuah string
ASCII_SIZE = 256
def maxFrequencyChar (str):
# Array untuk menyimpan frekuensi setiap karakter
# Menginisialisasi frekuensi setiap karakter sebagai 0
frekuensi = [0] * ASCII_SIZE
# Inisialisasi variabel maxFrequency
frekuensi maks = -1
# Inisialisasi variabel maxFrequencyChar
maxFrequencyChar = ''
# Melintasi dan memelihara
# frekuensi setiap karakter
untuk saya di str:
frekuensi[ordo (i)] += 1
untuk saya di str:
jika maxFrequency < frekuensi[ord (i)]:
maxFrequency = frekuensi[ord (i)]
maxFrequencyChar = i
kembalikan maxFrequencyChar
# Kode Pengemudi
str1 = "Penyihir yang mana?"
print("str1:", str1)
print("Karakter frekuensi tertinggi adalah:", maxFrequencyChar (str1))
str2 = "Dia melempar tiga lemparan bebas"
print("str2:", str2)
print("Karakter frekuensi tertinggi adalah:", maxFrequencyChar (str2))
str3 = "Eddie mengeditnya"
print("str3:", str3)
print("Karakter frekuensi tertinggi adalah:", maxFrequencyChar (str3))
str4 = "Menggunakan"
print("str4:", str4)
print("Karakter frekuensi tertinggi adalah:", maxFrequencyChar (str4))
str5 = "Dia melihat keju"
print("str5:", str5)
print("Karakter frekuensi tertinggi adalah:", maxFrequencyChar (str5))

Keluaran:

str1: Penyihir yang mana?
Karakter frekuensi tertinggi adalah: h
str2: Dia melempar tiga lemparan bebas
Karakter frekuensi tertinggi adalah: e
str3: Eddie mengeditnya
Karakter frekuensi tertinggi adalah: d
str4: Makeuseof
Karakter frekuensi tertinggi adalah: e
str5: Dia melihat keju
Karakter frekuensi tertinggi adalah: e

Program C untuk Menemukan Karakter Dengan Frekuensi Tertinggi

Di bawah ini adalah program C untuk mencari karakter dengan frekuensi tertinggi dalam sebuah string:

Terkait: Cara Menemukan Vokal, Konsonan, Digit, dan Karakter Khusus dalam String

// Program C untuk menemukan karakter
// memiliki frekuensi tertinggi dalam sebuah string
#sertakan 
#sertakan 
#tentukan ASCII_SIZE 256
menggunakan namespace std;
char maxFrequencyChar (char *str)
{
// Array untuk menyimpan frekuensi setiap karakter
// Menginisialisasi frekuensi setiap karakter sebagai 0
int frekuensi[ASCII_SIZE] = {0};
// Menemukan panjang string input
int lenOfStr = strlen(str);
// Inisialisasi variabel maxFrequency
int maxFrequency = 0;
// Inisialisasi variabel maxFrequencyChar
char maxFrequencyChar;
// Melintasi dan memelihara
// frekuensi setiap karakter
untuk (int i = 0; saya < lenOfStr; saya++)
{
frekuensi[str[i]]++;
if (maxFrequency < frekuensi[str[i]])
{
maxFrequency = frekuensi[str[i]];
maxFrequencyChar = str[i];
}
}
kembali maxFrequencyChar;
}
// Kode Pengemudi
int utama()
{
char str1[] = "Penyihir yang mana?";
printf("str1: %s", str1);
printf("Karakter frekuensi tertinggi adalah: %c \⁠n", maxFrequencyChar (str1));
char str2[] ​​= "Dia melempar tiga lemparan bebas";
printf("str2: %s", str2);
printf("Karakter frekuensi tertinggi adalah: %c \⁠n", maxFrequencyChar (str2));
char str3[] = "Eddie mengeditnya";
printf("str3: %s", str3);
printf("Karakter frekuensi tertinggi adalah: %c \⁠n", maxFrequencyChar (str3));
char str4[] = "Penggunaan";
printf("str4: %s", str4);
printf("Karakter frekuensi tertinggi adalah: %c \⁠n", maxFrequencyChar (str4));
char str5[] = "Dia melihat keju";
printf("str1: %s", str5);
printf("Karakter frekuensi tertinggi adalah: %c \⁠n", maxFrequencyChar (str5));
}

Keluaran:

str1: Penyihir yang mana?
Karakter frekuensi tertinggi adalah: h
str2: Dia melempar tiga lemparan bebas
Karakter frekuensi tertinggi adalah: e
str3: Eddie mengeditnya
Karakter frekuensi tertinggi adalah: d
str4: Makeuseof
Karakter frekuensi tertinggi adalah: e
str5: Dia melihat keju
Karakter frekuensi tertinggi adalah: e

Program JavaScript untuk Menemukan Karakter Dengan Frekuensi Tertinggi

Di bawah ini adalah program JavaScript untuk menemukan karakter dengan frekuensi tertinggi dalam sebuah string:

// Program JavaScript untuk menemukan karakter
// memiliki frekuensi tertinggi dalam sebuah string
biarkan ASCII_SIZE = 256;
fungsi maxFrequencyChar (str)
{
// Array untuk menyimpan frekuensi setiap karakter
// Menginisialisasi frekuensi setiap karakter sebagai 0
biarkan frekuensi = Array baru (ASCII_SIZE);
untuk (misalkan i = 0; i < ASCII_SIZE; saya++)
{
frekuensi[i] = 0;
}
// Menemukan panjang string input
misalkan lenOfStr = str.length;
untuk (misalkan i = 0; saya < lenOfStr; saya++)
{
frekuensi[str[i].charCodeAt (0)] += 1;
}
// Inisialisasi variabel maxFrequency
biarkan maxFrequency = -1;
// Inisialisasi variabel maxFrequencyChar
biarkan maxFrequencyChar = '';
// Melintasi dan memelihara
// frekuensi setiap karakter
untuk (misalkan i = 0; saya < lenOfStr; saya++)
{
if (maxFrequency < frekuensi[str[i].charCodeAt (0)])
{
maxFrequency = frekuensi[str[i].charCodeAt (0)];
maxFrequencyChar = str[i];
}
}
kembali maxFrequencyChar;
}
// Kode Pengemudi
let str1 = "Penyihir yang mana?";
document.write("str1: " + str1 + "
");
document.write("Karakter frekuensi tertinggi adalah: " + maxFrequencyChar (str1) + "
")
let str2 = "Dia melempar tiga lemparan bebas";
document.write("str2: " + str2 + "
");
document.write("Karakter frekuensi tertinggi adalah: " + maxFrequencyChar (str2) + "
")
let str3 = "Eddie mengeditnya";
document.write("str3: " + str3 + "
");
document.write("Karakter frekuensi tertinggi adalah: " + maxFrequencyChar (str3) + "
")
let str4 = "Menggunakan";
document.write("str4: " + str4 + "
");
document.write("Karakter frekuensi tertinggi adalah: " + maxFrequencyChar (str4) + "
")
let str5 = "Dia melihat keju";
document.write("str5: " + str5 + "
");
document.write("Karakter frekuensi tertinggi adalah: " + maxFrequencyChar (str5) + "
")

Keluaran:

str1: Penyihir yang mana?
Karakter frekuensi tertinggi adalah: h
str2: Dia melempar tiga lemparan bebas
Karakter frekuensi tertinggi adalah: e
str3: Eddie mengeditnya
Karakter frekuensi tertinggi adalah: d
str4: Makeuseof
Karakter frekuensi tertinggi adalah: e
str5: Dia melihat keju
Karakter frekuensi tertinggi adalah: e

Analisis Kompleksitas Waktu dan Ruang

Kompleksitas waktu dari maxFrequencyChar() fungsinya adalah Di). Kompleksitas ruang dari maxFrequencyChar() fungsinya adalah O(1) sebagai ruang tetap (Hash array). Itu tidak tergantung pada ukuran string input.

Notasi Big-O memberi Anda cara untuk menghitung berapa lama waktu yang dibutuhkan untuk menjalankan kode Anda. Ini adalah salah satu konsep yang paling penting untuk analisis algoritma. Jika Anda seorang programmer, Anda harus tahu tentang Notasi Big-O.

Yuvraj Chandra (30 Artikel Diterbitkan)

Yuvraj adalah mahasiswa sarjana Ilmu Komputer di University of Delhi, India. Dia bersemangat tentang Pengembangan Web Full Stack. Ketika dia tidak menulis, dia menjelajahi kedalaman teknologi yang berbeda.

More From Yuvraj Chandra