What is a String in Data Structure?

A String म्हणजेच characters चा एक क्रम (sequence) असतो. Programming मध्ये ही एक अत्यंत महत्वाची linear data structure आहे जी विविध applications मध्ये वापरली जाते.

Why are Strings Special?

• Small Alphabet Set: Normal arrays मध्ये elements large असू शकतात, पण strings मध्ये typically कमी characters असतात. उदा. English lowercase मध्ये फक्त 26 characters.
• Immutability: काही languages (Java, Python, JavaScript, C#) मध्ये strings immutable असतात. म्हणजे once बनली की ती change होत नाही.
• Optimizations Possible: String problems मध्ये character set लहान असल्यामुळे searching, counting, hashing fast होतं.

Basics of Strings

Introduction to Strings

String म्हणजे एका किंवा अधिक characters चा group, जो double quotes ” ” मध्ये define होतो. उदा. “Technorbit”, “DSA”, “Java”

String Implementations in Various Languages:

• C: Null terminated character array (char str[] = “Hello”;)
• C++: std::string class with powerful operations
• Java: String is immutable class
• Python: Immutable and flexible (str class)
• C#:String class
• JavaScript: Strings are primitive and immutable
• PHP: String is a data type, similar to JS

Basic String Operations:

Easy Level String Problems:

1. Check for Binary: फक्त 0 आणि 1 आहेत का string मध्ये?
2. Camel Case Conversion: camelCase मध्ये convert करा
3. Check for Palindrome: string पलटल्यावर same आहे का?
4. Check for Substring: दुसऱ्या string मध्ये आहे का?
5. Anagram Check: दोन strings मध्ये तेच characters आहेत का?
6. Duplicates: एकाच character ची किती वेळा repeat झाली आहे?
7. Left Rotate: String ला एका ठिकाणी rotate करा
8. IP Address Validation: IP valid आहे का?
9. URLify: Spaces replace करा with %20
10. Sort Characters: characters sort करा alphabetical order मध्ये

Medium Level String Challenges:

1. First Non-Repeating Character – पहिलं unique character शोधा
2. atoi Implementation – String to Integer convert करा
3. Add Binary Strings – दोन binary strings add करा
4. Roman to Integer – Roman numeral to decimal
5. Permutations of String – सर्व permutations generate करा
6. Longest Palindromic Substring – सर्वात मोठं palindrome substring शोधा
7. Count Anagram Substrings – किती anagram substrings आहेत?
8. Word Break Problem – दिलेला string word list मधून divide होतो का?

Hard Level String Challenges:

1. Lexicographic Rank of a String – दिलेल्या string चा alphabetical order मध्ये rank
2. Multiply Large Numbers as Strings – large numbers store करताना overflow टाळण्यासाठी string वापरून multiplication
3. Alien Dictionary – alien language मध्ये order शोधणे
4. Palindrome Substring Queries – दिलेल्या substring palindrome आहे का?
5. Word Wrap Problem – Space optimize करत word wrap करा
6. Minimum Bracket Reversals – expression balance करण्यासाठी किती brackets reverse करावेत?
7. Decode Encoded String – 3[a2[bc]] सारखी string decode करा

Advance Concepts and Techniques:

• Prefix Sum in Strings – Fast substring queries साठी
• KMP Algorithm – Pattern Searching
• Z-Algorithm – Efficient substring search
• Rabin-Karp – Rolling Hashing technique
• Trie for Dictionary Matching – Auto-complete systems
• Sliding Window Technique – Substring problems optimize करणे
• HashMaps and Frequency Counters – Occurrence based queries

Practical Applications:

• Text Processing Systems
• Spell Checkers and Grammar Tools
• Compilers आणि Parsers
• Search Engines
• DNA Pattern Matching
• Chat & Messaging Systems

Tips

• Interview मध्ये palindrome, anagram आणि substring problems frequently विचारले जातात
• Real-time systems मध्ये string immutability thread safety साठी useful असते
• Competitive coding साठी KMP, Z-Algorithm, and Try must learn करा