DEV Community: ozlab

The Longest Palindromic Sub-string - Part 2

ozlab — Thu, 24 Feb 2022 00:16:10 +0000

Yesterday is a palindrome day! 22022022!

And I remembered I talked about a palindromic sub-string problem on Leetcode in this post. I used Manacher's Algorithm to solve it. It's efficient but really hard to get it right in one go. Especially for me :(

The easy way

So I've got a much easier version here - yet not super efficient. But it's really easier, to understand and to write. I got it right at the first try.

The idea is, from each character in the string, using two indexes (pointers) going left and right to check both characters, until they are different. For instance for the string

"a b c d e f e d g h i"

The blue arrow indicates that we go through each character of the string, and the red arrows indicate two pointers, starting from each character, going one step each time to left and right, checking if the current characters are the same or not. If same, then we are having a palindromic string at the moment, so we can go check the next left and right characters.

We also need to think about the case of even characters:

We can write a function to return the palindromic sub-string, given the whole string and the character index (the blue arrow pointing to) as the parameters:

string palindrome(string& s, int l, int r) {
    while (l >= 0 && r < s.size() && s[l] == s[r]) {
        l--;
        r++;
    }        
    return s.substr(l + 1, r - l - 1);
}

For a string with odd number of characters, call the function with l = r; otherwise for an "even string", call it with r = l + 1

The solution is as below. 42 ms, 22.7 MB.

class Solution {
public:
    string longestPalindrome(string s) {
        string oddStr, evenStr;
        string ret = "";

        // Go through each character of the string
        for (int i = 0; i < s.size(); i++) {
            // As mentioned, we need to think about both odd and even characters
            oddStr = palindrome(s, i, i);
            evenStr = palindrome(s, i, i + 1);

            // Check if the current palindrome is the longest
            // If yes, update ret
            if (oddStr.size() > evenStr.size()){
                if (oddStr.size() > ret.size()) {
                    ret = oddStr;
                }
            } else {
                if (evenStr.size() > ret.size()) {
                    ret = evenStr;
                }                
            }
        }

        return ret;
    }

    string palindrome(string& s, int l, int r) {
        // If the characters the left and right pointers are pointing to are the same
        // Then we currently have a palindrome, 
        // so we can go to check the next characters
        while (l >= 0 && r < s.size() && s[l] == s[r]) {
            l--;
            r++;
        }

        return s.substr(l + 1, r - l - 1);
    }
};

All I Know About Decibel (dB) - Part 2

ozlab — Tue, 22 Feb 2022 00:48:37 +0000

As Part 1 introduces, we get decibel using the formula

\times log \frac{p_1}{p_2} (dB)

I'd blame my poor English ability that I didn't realise what the name decibel really meant for quite a few years. It's called deci-bel so apparently there's a Bel first.

The bel (B) and the smaller decibel (dB) are units of measurement of sound pressure level (SPL) invented by Bell Labs and named after him

from: Wikipedia

That's him! As stated, using deci-, people can make bel smaller, and meanwhile we have to add the $10× \times$ in the formula, to make bel become decibel.

You might notice that when talking about voltage and current, the formula becomes

20 \times log \frac{p_1}{p_2} (dB)

So why 20 here? I was very confused. I asked around and got this answer: For measuring something like a magnitude, we use $20× \times$ , otherwise for the power stuffs, use $10× \times$ ... Okay then it's time to test my English again: what kind of thing is a magnitude? And what is not? I reckon it's a correct but not so good answer.

Finally I met a guy, he took out a piece of paper and wrote some high school maths on it:

\times I=U \times (U/R) = U^2 / R

Yeah that's Ohm's Law, I get it. Then if $P_r$ and $U_r$ are the references and $U$ is the voltage we are measuring, from the original $10× \times$ formula we have:

10 \times log (P / P_r)

\times log ((U^2/R)/(U_r^2/R))

\times log (U/U_r)^2

\times 10 \times log (U/U_r) = 20 \times log (U/U_r)

That's how $20× \times$ comes up. Same process for the current (Use $P=I2×RP=I^2 \times R$ ). Maths can be scary, but useful.

from OZLab

All I Know About Decibel (dB) - Part 1

ozlab — Fri, 18 Feb 2022 13:17:42 +0000

Most people know that dB (decibel) is a unit, you use it when you want to tell the level of a sound. People could say, the sound of a jet engine can hit up to 140 dB; or the sound level of a normal human talking is about 60~70 dB, etc.

If I explained dB like above to my boss, I would definitely be doomed.

To avoid the embarrassing conversation, I quickly did some learning. I learnt that:

dB is actually a ratio
Because it's a ratio, there must be two things to make a fraction
The ratio tells us the difference between the two things
We use a logarithmic way to describe that ratio

If we still take the case of sound loudness, for instance, say the two things are two sounds:

The first sound is played with the power of $p_1$
The second sound is played with the power of $p_2$

So we can get the dB like this:

\times log \frac{p_1}{p_2} (dB)

where the $l o g$ is to base $10$

Now we can say that comparing to the second sound, the first sound is $l$ dB. Note it always should be

comparing to another value, this one is some dB

If we only say some sound is some dB, it doesn't really make sense. So that's right, when people say the sound level of a jet engine is 140 dB, they actually mean

comparing to another value, the sound level of a jet engine is 140 dB

Even though they usually don't know that. And that another value, which we call it the reference, is normally a very small sound pressure level, like 20 micropascals ( $\mu Pa$ ).

Some dB units

Now it's easier to explain some 'dB units' we see. They actually just have different references.

For example: dBm. It uses 1 milliwatt (1 mW) as the reference:

10 \times log \frac{P}{1 mW} (dBm)

So we can say P is 10 dBm, or P is -30 dBm... It's gonna be an absolute value, no need to mention "when compared to some value (the reference), P is blah blah blah..." anymore.

The following units are also common:

dBμ - reference is 1 microwatt (1 μW)
dBmV - reference is 1 millivolt (1 mV)
dBi - reference is an isotropic antenna which has a gain of 0 dB in a specific direction
dBFS - reference is the full scale - More details on Wikipedia

Now this answer could make my boss happy for the day, or even for the week, if I was lucky enough. That's why I have to have Part 2 here.

from: OZLab

The Longest Palindromic Sub-string

ozlab — Fri, 18 Feb 2022 13:06:57 +0000

I saw this problem on LeetCode couple of years ago: Longest Palindromic Substring

I used to browse problems on LeetCode every time before I was seeking for a new job. But, you know, it's pretty relaxing. I mean, if I found that i couldn't solve a problem easily, I just gave up. No pressure.

Take this Longest Palindromic Substring for example, I met it a few times before, I knew there is an algorithm called Manacher can solve this. But I've never worked it out even though I knew about the algorithm. Let me try again today.

The first idea came into my head was, find all the palindromic sub-strings and check their lengths. It sounds like crazy but it's actually a viable plan. To make it work, we need to check each character and find out the palindromic sub-string that centered with this character. We can store the "radius" of the palindromic sub-string for each character in the original string, then find out the longest one. So the radius obvious can be 1 or more.

For example, for the character d in string

a b c d c b x

the radius is 3 (d, c, b). For character b, its radius is 1 (only including b itself).

The problem is, for a super long string, calculating the radius for each palindromic string is not efficient. We have to find a way to avoid always accumulating the radius from 1.

The Manacher's algorithm is based on this idea.

Diagram 1

We are going to find out the longest palindromic sub-string in a string s
We go through each character from left to right, and put the radius of the palindromic sub-string (which centered with the current character) into an array P.
So far the radius (on the right) of the palindromic sub-string with the centre character s[idx] can reach the position maxRight, which is the most right position among all the palindromic sub-strings.
At the moment we are at the character s[i]. We are going to find the radius of Pi and save it in P[i].

Before we start, we need to handle this issue first: if a palindromic string has even number of characters, the centre of it is a space between two characters

If a string has odd number of character(s), the centre is a character:

So the first step of this Manacher algorithm is, eliminating this ambiguity by inserting an arbitrary character (that doesn't appear in the string), say "#", between every two characters of the string:

Diagram 2

When i < maxRight, the whole Pi or part of Pi has a "mirror" on the other side of idx. This "mirror" is Pj. Its centre character is s[j].
- If P[j] is relatively small - the whole Pj is included in Pidx (See Diagram 1): We find the initial value of P[i]. That is, P[i] = P[j]. Then with i as the centre, we expand Pi until it's not palindromic any more or reach the end of s.
- If P[j] is relatively large - part of Pj is outside Pidx (See Diagram 2): The initial value of P[i] is maxRight - i. Then with i as the centre, we expand Pi until it's not palindromic any more or reach the end of s.
When i > maxRight, it means there is no history record can be used to calculate Pi, so P[i] will start from 1.

So the critical part of this algorithm: what is the initial value of P[i]? The answer is:

P[i] = min(P[j], maxRight - i);

And here's how to get P[j]: From Diagram 1 we can easily get that idx - j = i - idx, so j = 2 * idx -i.

Now we know the position of the longest palindromic sub-string centre and its radius, so we can get its start position and then work out what this sub-string is. The following code is what I submitted to Leetcode, I'm happy with the 12 ms runtime and 10 MB memory used.

class Solution {
public:
    string longestPalindrome(string s) {
        string retStr = s;
        int newLen = s.length() * 2 + 1;

        // First step: Insert "#" to make the string size an odd number
        for (int i = 0; i < newLen; i += 2)
        {
            retStr = retStr.insert(i, "#");
        }
        retStr.insert(0, "$");


        // Process retStr
        vector<int> p(retStr.size(), 0);
        int mx = 0, id = 0, resLen = 0, resCenter = 0;
        for (int i = 1; i < retStr.size(); ++i) {
            p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
            while (retStr[i + p[i]] == retStr[i - p[i]]) ++p[i];
            if (mx < i + p[i]) {
                mx = i + p[i];
                id = i;
            }
            if (resLen < p[i]) {
                resLen = p[i];
                resCenter = i;
            }
        }
        return s.substr((resCenter - resLen) / 2, resLen - 1);
    }
};

from: OZLab