


2696. Minimum String Length After Removing Substrings
Difficulty: Easy
Topics: String, Stack, Simulation
You are given a string s consisting only of uppercase English letters.
You can apply some operations to this string where, in one operation, you can remove any occurrence of one of the substrings "AB" or "CD" from s.
Return the minimum possible length of the resulting string that you can obtain.
Note that the string concatenates after removing the substring and could produce new "AB" or "CD" substrings.
Example 1:
- Input: s = "ABFCACDB"
- Output: 2
-
Explanation: We can do the following operations:
- Remove the substring "ABFCACDB", so s = "FCACDB".
- Remove the substring "FCACDB", so s = "FCAB".
- Remove the substring "FCAB", so s = "FC".
- So the resulting length of the string is 2.
- It can be shown that it is the minimum length that we can obtain.
Example 2:
- Input: s = "ACBBD"
- Output: 5
- Explanation: We cannot do any operations on the string so the length remains the same.
Constraints:
- 1
- s consists only of uppercase English letters.
Hint:
- Can we use brute force to solve the problem?
- Repeatedly traverse the string to find and remove the substrings “AB” and “CD” until no more occurrences exist.
Solution:
We'll use a stack to handle the removal of substrings "AB" and "CD". The stack approach ensures that we efficiently remove these substrings as they occur during traversal of the string.
Approach:
-
Use a Stack:
- Traverse the string character by character.
- Push each character onto the stack.
- If the top two characters on the stack form the substring "AB" or "CD", pop these two characters from the stack (remove them).
- Continue this process for all characters in the input string.
-
Final String:
- At the end of the traversal, the stack will contain the reduced string.
- The minimum possible length will be the size of the stack.
Let's implement this solution in PHP: 2696. Minimum String Length After Removing Substrings
<?php <br> /**
- @param String $s
- @return Integer /
- go to ./solution.php */
// Example usage:
echo minLengthAfterRemovals("ABFCACDB"); // Output: 2
echo "\n";
echo minLengthAfterRemovals("ACBBD"); // Output: 5
?>
Explanation:
- We initialize an empty stack ($stack).
- Loop through each character of the string s.
- Check the top character of the stack:
- If the top character and the current character form the substrings "AB" or "CD", we remove the top character using array_pop.
- Otherwise, push the current character onto the stack.
- The stack will hold the characters that remain after all possible removals.
- Finally, count($stack) gives the length of the resulting string.
Complexity:
- Time Complexity: O(n), where n is the length of the string. Each character is processed at most twice (once pushed, once popped).
- Space Complexity: O(n) for the stack, in the worst case where no removals are possible.
This solution effectively minimizes the string by removing all possible occurrences of "AB" and "CD" until no more can be found.
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks ?. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
- GitHub
Atas ialah kandungan terperinci Panjang Rentetan Minimum Selepas Mengeluarkan Substring. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

URL panjang, sering berantakan dengan kata kunci dan parameter penjejakan, boleh menghalang pelawat. Skrip pemendekan URL menawarkan penyelesaian, mewujudkan pautan ringkas yang sesuai untuk media sosial dan platform lain. Skrip ini sangat berharga untuk laman web individu a

Berikutan pengambilalihan berprofil tinggi oleh Facebook pada tahun 2012, Instagram mengadopsi dua set API untuk kegunaan pihak ketiga. Ini adalah API Grafik Instagram dan API Paparan Asas Instagram. Sebagai pemaju membina aplikasi yang memerlukan maklumat dari a

Laravel memudahkan mengendalikan data sesi sementara menggunakan kaedah flash intuitifnya. Ini sesuai untuk memaparkan mesej ringkas, makluman, atau pemberitahuan dalam permohonan anda. Data hanya berterusan untuk permintaan seterusnya secara lalai: $ permintaan-

Ini adalah bahagian kedua dan terakhir siri untuk membina aplikasi React dengan back-end Laravel. Di bahagian pertama siri ini, kami mencipta API RESTful menggunakan Laravel untuk aplikasi penyenaraian produk asas. Dalam tutorial ini, kita akan menjadi dev

Laravel menyediakan sintaks simulasi respons HTTP ringkas, memudahkan ujian interaksi HTTP. Pendekatan ini dengan ketara mengurangkan redundansi kod semasa membuat simulasi ujian anda lebih intuitif. Pelaksanaan asas menyediakan pelbagai jenis pintasan jenis tindak balas: Gunakan Illuminate \ Support \ Facades \ http; Http :: palsu ([ 'Google.com' => 'Hello World', 'github.com' => ['foo' => 'bar'], 'forge.laravel.com' =>

Pelanjutan URL Pelanggan PHP (CURL) adalah alat yang berkuasa untuk pemaju, membolehkan interaksi lancar dengan pelayan jauh dan API rehat. Dengan memanfaatkan libcurl, perpustakaan pemindahan fail multi-protokol yang dihormati, php curl memudahkan execu yang cekap

Adakah anda ingin memberikan penyelesaian segera, segera kepada masalah yang paling mendesak pelanggan anda? Sembang langsung membolehkan anda mempunyai perbualan masa nyata dengan pelanggan dan menyelesaikan masalah mereka dengan serta-merta. Ia membolehkan anda memberikan perkhidmatan yang lebih pantas kepada adat anda

Tinjauan Landskap PHP 2025 menyiasat trend pembangunan PHP semasa. Ia meneroka penggunaan rangka kerja, kaedah penempatan, dan cabaran, yang bertujuan memberi gambaran kepada pemaju dan perniagaan. Tinjauan ini menjangkakan pertumbuhan dalam PHP Versio moden


Alat AI Hot

Undresser.AI Undress
Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover
Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool
Gambar buka pakaian secara percuma

Clothoff.io
Penyingkiran pakaian AI

AI Hentai Generator
Menjana ai hentai secara percuma.

Artikel Panas

Alat panas

ZendStudio 13.5.1 Mac
Persekitaran pembangunan bersepadu PHP yang berkuasa

Penyesuai Pelayan SAP NetWeaver untuk Eclipse
Integrasikan Eclipse dengan pelayan aplikasi SAP NetWeaver.

EditPlus versi Cina retak
Saiz kecil, penyerlahan sintaks, tidak menyokong fungsi gesaan kod

DVWA
Damn Vulnerable Web App (DVWA) ialah aplikasi web PHP/MySQL yang sangat terdedah. Matlamat utamanya adalah untuk menjadi bantuan bagi profesional keselamatan untuk menguji kemahiran dan alatan mereka dalam persekitaran undang-undang, untuk membantu pembangun web lebih memahami proses mengamankan aplikasi web, dan untuk membantu guru/pelajar mengajar/belajar dalam persekitaran bilik darjah Aplikasi web keselamatan. Matlamat DVWA adalah untuk mempraktikkan beberapa kelemahan web yang paling biasa melalui antara muka yang mudah dan mudah, dengan pelbagai tahap kesukaran. Sila ambil perhatian bahawa perisian ini

Muat turun versi mac editor Atom
Editor sumber terbuka yang paling popular
