Temukan Substring Terpanjang tanpa Mengulangi Karakter

1. Ikhtisar

Dalam tutorial ini, bandingkan cara menemukan substring terpanjang dari huruf unik menggunakan Java. Misalnya, substring terpanjang dari huruf unik di "CODINGISAWESOME" adalah "NGISAWE".

2. Pendekatan Brute Force

Mari kita mulai dengan pendekatan yang naif. Untuk memulainya, kita dapat memeriksa setiap substring apakah itu berisi karakter unik:

String getUniqueCharacterSubstringBruteForce(String input) { String output = ""; for (int start = 0; start < input.length(); start++) { Set visited = new HashSet(); int end = start; for (; end < input.length(); end++) { char currChar = input.charAt(end); if (visited.contains(currChar)) { break; } else { visited.add(currChar); } } if (output.length() < end - start + 1) { output = input.substring(start, end); } } return output; }

Karena ada n * (n + 1) / 2 kemungkinan substring, kompleksitas waktu dari pendekatan ini adalah O (n ^ 2) .

3. Pendekatan yang Dioptimalkan

Sekarang, mari kita lihat pendekatan yang dioptimalkan. Kami mulai melintasi string dari kiri ke kanan dan mempertahankan jalur:

  1. substring saat ini dengan karakter yang tidak berulang dengan bantuan indeks awal dan akhir
  2. output substring non-berulang terpanjang
  3. tabel pencarian karakter yang sudah dikunjungi
String getUniqueCharacterSubstring(String input) { Map visited = new HashMap(); String output = ""; for (int start = 0, end = 0; end < input.length(); end++) { char currChar = input.charAt(end); if (visited.containsKey(currChar)) { start = Math.max(visited.get(currChar)+1, start); } if (output.length() < end - start + 1) { output = input.substring(start, end + 1); } visited.put(currChar, end); } return output; }

Untuk setiap karakter baru, kami mencarinya di karakter yang sudah dikunjungi. Jika karakter telah dikunjungi dan merupakan bagian dari substring saat ini dengan karakter yang tidak berulang, kami memperbarui indeks awal. Jika tidak, kami akan melanjutkan melintasi string.

Karena kita melintasi string hanya sekali, kompleksitas waktu akan linier, atau O (n) .

Pendekatan ini juga dikenal sebagai pola jendela geser.

4. Pengujian

Terakhir, mari kita uji implementasi kita secara menyeluruh untuk memastikannya berfungsi:

@Test void givenString_whenGetUniqueCharacterSubstringCalled_thenResultFoundAsExpected() {  assertEquals("", getUniqueCharacterSubstring(""));   assertEquals("A", getUniqueCharacterSubstring("A")); assertEquals("ABCDEF", getUniqueCharacterSubstring("AABCDEF")); assertEquals("ABCDEF", getUniqueCharacterSubstring("ABCDEFF")); assertEquals("NGISAWE", getUniqueCharacterSubstring("CODINGISAWESOME")); assertEquals("be coding", getUniqueCharacterSubstring("always be coding")); }

Di sini, kami mencoba dan menguji kondisi batas serta kasus penggunaan yang lebih umum .

5. Kesimpulan

Dalam tutorial ini, kita telah mempelajari cara menggunakan teknik jendela geser untuk menemukan substring terpanjang dengan karakter yang tidak berulang.

Dan, seperti biasa, kode sumber tersedia di GitHub.