Cari Substring Terpanjang tanpa Mengulang Karakter

1. Gambaran keseluruhan

Dalam tutorial ini, bandingkan cara untuk mencari substring huruf unik terpanjang menggunakan Java. Contohnya, substring huruf unik terpanjang dalam "CODINGISAWESOME" adalah "NGISAWE".

2. Pendekatan Brute Force

Mari kita mulakan dengan pendekatan naif. Sebagai permulaan, kita dapat memeriksa setiap substring sama ada mengandungi watak 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; }

Oleh kerana terdapat kemungkinan substring n * (n + 1) / 2 , kerumitan masa pendekatan ini adalah O (n ^ 2) .

3. Pendekatan yang Dioptimumkan

Sekarang, mari kita lihat pendekatan yang dioptimumkan. Kami mula melintasi rentetan dari kiri ke kanan dan memantau:

  1. substring semasa dengan watak yang tidak berulang dengan bantuan indeks permulaan dan akhir
  2. output substring terpanjang yang tidak berulang
  3. jadual pencarian watak 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 watak baru, kami mencarinya dalam watak yang sudah dikunjungi. Sekiranya watak telah dikunjungi dan merupakan sebahagian daripada substring semasa dengan watak yang tidak berulang, kami mengemas kini indeks permulaan. Jika tidak, kami akan terus menerjah rentetan.

Oleh kerana kita melintasi rentetan hanya sekali, kerumitan waktu akan linear, atau O (n) .

Pendekatan ini juga dikenali sebagai corak tingkap gelongsor.

4. Ujian

Akhirnya, mari kita uji secara menyeluruh pelaksanaan kami untuk memastikan ia 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 mencuba dan menguji keadaan sempadan serta kes penggunaan yang lebih biasa .

5. Kesimpulan

Dalam tutorial ini, kami telah mempelajari cara menggunakan teknik sliding window untuk mencari substring terpanjang dengan watak yang tidak berulang.

Dan, seperti biasa, kod sumber tersedia di GitHub.