string related oa questions – linlin’s posts

Today I am gonna to go through some string related OA questions. I will keep updating this post when I get new string questions.

String is one of the most common primitive data type in most programming languages. Some very interesting questions about string manuplications or checkings come out. Without further ado, let’s get started!

Longest Substring Without Repeating Characters

Problem Statement

Here goes the description in leetcode^[1]:

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

Solutions

The naive way to solve it is brute force. We can iterate the string and check each substring whether it has no repeated characters. By this way, the time complexity would be $O(n^3)$.

We can solve it more

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Set<Character> substrset = new HashSet<Character>();
        int longest = 0;
        int idx = 0;
        String tmpstr = "";
        while (idx != n) {
            char c = s.charAt(idx);
            idx ++;
            if (substrset.contains(c)) {
                longest = (longest >= tmpstr.length() ? longest : tmpstr.length());
                String removestr = tmpstr.substring(0, tmpstr.indexOf(c)+1);
                tmpstr = tmpstr.substring(tmpstr.indexOf(c)+1) + c;
                substrset.removeAll(Arrays.asList(removestr.toCharArray()));
                substrset.add(c);
            } else {
                tmpstr += c;
                substrset.add(c);
            }
        }
        longest = (longest >= tmpstr.length() ? longest : tmpstr.length());
        return longest;
    }
}

Longest Palindromic Substring

Problem Statemetn

Here goes the description in leetcode about palindromic substring^[2]:

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

Solutions

ZigZag Conversion

Problem Statement

The description about ZigZag conversion in leetcode^[3]:

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

Solutions

Reference

1. Longest Substring Without Repeating Characters
2. Longest Palindromic Substring
3. ZigZag Conversion