Intro to C++ Strings

Char Arrays in C

C++ Strings

C style char arrays work in C++ as well. However, C++ provides string, which is much more powerful than C arrays.

String declaration :

string A; // declares an empty string
string A = "Hello"; // declares string initialized to "Hello".

Accessing the ith element :

A[i] // O(1)

Size ( number of elements ) of the string :

A.length()  // O(1)

Appending to the string

Another String

A += "Hello"; // Appends Hello to the string. O(n) operation

Single Character

A.push_back('H'); // Append character H to the string. 
// O(1) operation.

String Simulation Questions

Question 1: Longest Common Prefix

Given the array of strings A, you need to find the longest string S, which is the prefix of ALL the strings in the array.

The longest common prefix for a pair of strings S1 and S2 is the longest string S, which is the prefix of both S1
and S2.

For Example, the longest common prefix of "abcdefgh" and "abcefgh" is "abc".

For Example

Input 1:
    A = ["abcdefgh", "aefghijk", "abcefgh"]
Output 1:
    "a"
    Explanation 1:
        Longest common prefix of all the strings is "a".
Input 2:
    A = ["abab", "ab", "abcd"];
Output 2:
    "ab"
    Explanation 2:
        Longest common prefix of all the strings is "ab".

Solution:

Note: the prefix has to be the prefix of ALL the strings.

So, you can pick any random string from the array and start checking its characters from the beginning to see if they can be a part of the common substring.

string Solution::longestCommonPrefix(vector<string> &strs) {
  
    if (strs.size() == 0) return "";
            string ans = "";
            for (int i = 0; i < strs[0].length(); i++) {
                // checking if character i qualifies to be in the answer. 
                bool isQualified = true; 
                for (int j = 1; j < strs.size(); j++) {
                    if (i >= strs[j].length() || strs[j][i] != strs[0][i]) {
                        isQualified = false;
                        break;
                    }
                }
                if (!isQualified) break;
                ans.push_back(strs[0][i]);
            }
            return ans;
}

String Search Questions

Question 2: Implement StrStr

strstr — locate a substring ( needle ) in a string ( haystack ).

Returns the index of the first occurrence of needle in the haystack, or -1 if the needle is not part of the haystack.

Solution:

Let us first think about a simpler problem. How do you find out if 2 strings are equal?

Implementing strstr is just plain simple simulation.

Consider every index i for the answer. Find if the following 2 strings are equal:

1) Needle string and,

2) String haystack from index i with length the same as needle’s length

Note that this solution's complexity is O(M*N), where M is the length of the haystack and N is the length of the needle.

bool isEqual(const string A, const string B, int n, int m, int i) {
    for(int j = 0; j < m; j ++)
        if(A[j+i] != B[j])
            return false;
    return true;
}

int Solution::strStr(const string A, const string B) {
    if(A.size() == 0 || B.size() == 0)
        return -1;
    int n = A.size();
    int m = B.size();
    for(int i = 0; i < (n-m+1); i ++)
        if(isEqual(A, B, n, m, i))
            return i;
    return -1;
}

Note: To solve it in O(M), we can use the KMP algorithm:

String Trick Questions

Question 3: Minimum Parentheses!

Given a string A of parentheses ‘(‘ or ‘).’

The task is to find the minimum number of parentheses ‘(‘ or ‘)’ (at any positions) we must add to make the resulting parentheses string valid.

A string is valid if:

• Open brackets must be closed by the corresponding closing bracket.
• Open brackets must be closed in the correct order.

Problem Constraints

1 <= |A| <= 105

A[i] = ‘(‘ or A[i] = ‘)’

Input Format

First and only argument is an string A.

Output Format

Return a single integer denoting the minimum number of parentheses ‘(‘ or ‘)’ (at any positions) we must add in A to make the resulting parentheses string valid.

Example Input

Input 1:

A = "())"

Input 2:

A = "((("

Example Output

Output 1:

1

Output 2:

3

Example Explanation

Explanation 1:

One '(' is required at beginning.

Explanation 2:

Three ')' is required at end.

Solution:

First, try to find a solution to check whether a string is valid or not.

For each extra ‘),’ we need to add a corresponding ‘(‘ at the start of the string.

We keep track of the balance of the string i:e the number of ‘(‘ minus the number of ‘).’ A string is valid if its balance is 0, every prefix has a non-negative balance.

Now, consider the balance of every prefix of A. If it is ever negative (say, -1), we must add a ‘(‘ bracket at the beginning. Also, if the balance of S is positive (say, +P), we must add P times ‘)’ brackets at the end.

Time Complexity: O(n) where n=A.length()

int Solution::solve(string a) {
    int openBrackets = 0, req=0;
    for(int i=0;i<a.length();i++) {
        if(a[i]=='(') {
            openBrackets++;
        } else {
            if(openBrackets>0) openBrackets--;
            else {
                req++;
            }
        }
    }
    req+=openBrackets;
    return req;
}

Word Questions

Question 4: Length of Last Word

Given a string s consists of upper/lower-case alphabets and space characters ' ', return the length of the last word in the string.

If the last word does not exist, return. 0.

Note: A word is defined as a character sequence consists of non-space characters only.

Example:

Given s = "Hello World",

return 5 as length("World") = 5.

Solution:

Not using library functions and traversing the string only once is the main twist here.

Try to answer these questions while using a single loop:
How can you detect the end of the string?
How can you detect where the word begins?

What if you maintained the length of the current word?

You reset the word's length when the next word begins (When does a new word begin?)

Return the last length you have.

int Solution::lengthOfLastWord(const string A) {
    
    int cnt=0;
    int i=A.length()-1;
    while(A[i]==' ') //looping from last and encountering a first alphanumeric character
        i--;
        
    for(;i>=0 && A[i]!=' ';i--) //from that point to the first space encountered
        cnt++;
    
    return cnt;
}

String Parsing Questions

Question 5: Atoi

Implement atoi to convert a string to an integer.

Example :

Input : "9 2704"
Output : 9

Solution:

We only need to handle four cases:

1. Discards all leading whitespaces
2. Sign of the number
3. Overflow
4. Invalid input

Detecting overflow gets tricky. It would help if you detected overflow before the number is about to overflow.

So:

• If the number is positive and the current number is greater than MAX_INT/10, and you are about to append a digit, your number will certainly overflow.
• If the current number = MAX_INT / 10, then based on the last digit, we can detect if the number will overflow.

int atoi(const string &str) {
            int sign = 1, base = 0, i = 0;
            while (str[i] == ' ') { i++; }
            if (str[i] == '-' || str[i] == '+') {
                sign = (str[i++] == '-') ? -1 : 1; 
            }
            while (str[i] >= '0' && str[i] <= '9') {
                if (base >  INT_MAX / 10 || (base == INT_MAX / 10 && str[i] - '0' > 7)) {
                    if (sign == 1) return INT_MAX;
                    else return INT_MIN;
                }
                base  = 10 * base + (str[i++] - '0');
            }
            return base * sign;
        }

String Math Questions

Question 6: Roman To Integer

Given a string A representing a roman numeral.
Convert A into an integer.

A is guaranteed to be within the range from 1 to 3999.

For Example

Input 1:
    A = "XIV"
Output 1:
    14
Input 2:
    A = "XX"
Output 2:
    20

Solution:

Note how the number XVI(10+5+1) and XIV(10–1+5) differ.

In one case, we are adding the numeric value of a letter, and in other cases, we are subtracting it. How can you simulate this?

The key is to notice that the letter with the most value always occurs at the string's start in a valid Roman numeral representation.

Whenever a letter with a lesser value precedes a higher value letter, it means its value has to be added as negative of that letter’s value.

In all other cases, the values get added.

Author: https://www.linkedin.com/in/shivam-ross/ | https://twitter.com/BeastofBayArea | https://www.instagram.com/sup.its.shiv/