Tiêu đề Strings.pdf ✅

Strings Topics 1. Definition of a String 2. Problems & Solutions 3. Important References
Definition of a String In computer science a string is any finite sequence of characters (i.e., letters, numerals, symbols and punctuation marks). An important characteristic of each string is its length, which is the number of characters in it. The length can be any natural number (i.e., zero or any positive integer). A particularly useful string for some programming applications is the empty string, which is a string containing no characters and thus having a length of zero. A substring is any contiguous sequence of characters in a string. The String Data Type How strings and string data types are represented depends largely on the character set (e.g., an alphabet) for which they are defined and the method of character encoding (i.e., how they are represented by bits on a computer). String implementations (formerly) were usually designed to work with ASCII (the de facto standard for the character encoding used by computers and communications equipment to represent text) or with its subsequent extensions. In recent years, however, the trend has been to implement strings with Unicode, which attempts to provide character codes for all existing and extinct written languages. The Programming Languages that use ASCII style character encoding are notably C & C++. The Programming Languages that use Unicode style character encoding are notably Java & Python3. How Do Popular Languages Handle Strings? 1. C: a. Basics of C Strings. b. Character Array & Character Pointer. c. NYU Material on Strings in C. d. WikiBook on C Strings. [The aforementioned articles/links are a must read, for all programmers] 2. C++: a. Basics of C++ Strings. b. library in C++ STL. 3. Java: a. Basics of String Class. b. Official Documentation of String Class. 4. Python: a. Official Documentation on Strings in Python 3. b. Python Strings by Google.
Problems & Solutions 1. Given a string, WAP to count the number of occurrences of each character. [Assume that the string only has lowercase english characters] Solutions ○ Approach #1: Maintain an array called count[26]. While iterating over the string str, increment the count of each character referring to their respective positions in the count[] array by executing count[str[i]-'a']++. Time Complexity: O(N), Space Complexity: O(26) = O(1) ○ Approach #2: Maintain a HashMap cnt; and while iterating through the string str, just add any new character into the HashMap with value 1 by executing cnt.add(str[i],1); or if the character is already inserted into the HashMap, then simply increment the character’s value by 1 in the HashMap by executing cnt[str[i]]++; Time Complexity: O(N), Space Complexity: O(26) = O(1) Note: Search/Insert/Delete in Unordered HashMap takes O(1) on an average case. Hence Approach-1 is better than Approach-2. 2. Given a string, WAP to convert all its lowercase characters, to uppercase characters and convert all its uppercase characters to its equivalent lowercase characters. Example: Given string: "sMaRt inTerViewS" Expected Output: "SmArT INtERvIEWs" Solutions ○ Approach #1: While iterating through each character in the string, if the character is an uppercase character, then add 32 to that character, and if the character is a lowercase character, then subtract 32 from that character. Ignore all the characters which are special symbols and digits. Time Complexity: O(N), Space Complexity: O(1) ○ Approach #2: For a string str, we can XOR each character in str with 32. [Hint: Understand the bit representation of each uppercase and lowercase character in the character set to understand why this solution works]. Time Complexity: O(N), Space Complexity: O(1) 3. Given two strings A & B, check if both strings are anagrams of each other. [Defn of Anagram: Anagrams are two/more strings of same size which have the same exact characters in each of the strings. Any permutation of a string, is it’s anagram.] Example 1: A = "listen"; B = "silent"; {Here, both A & B are anagrams of each other} Example 2: A = "smart"; B = "stack"; {Here, both A & B are not anagrams of each other} Solutions [Note: Check if both strings A & B are equal in length before applying any approach. If A.size() != B.size(), then both strings A & B are not anagrams of each other]