CODEWITHSUNDEEP
javaalgorithmdivide-and-conquer
P.K.
P.K.

Reputation: 409

Reasoning behind using a divide and conquer approach

I am trying to solve this question on LeetCode:

A string s is nice if, for every letter of the alphabet that s contains, it appears both in uppercase and lowercase. For example, "abABB" is nice because 'A' and 'a' appear, and 'B' and 'b' appear. However, "abA" is not because 'b' appears, but 'B' does not.
Given a string s, return the longest substring of s that is nice. If there are multiple, return the substring of the earliest occurrence. If there are none, return an empty string.
For s = "YazaAay", the expected output is: "aAa"

One of the top voted solutions uses a Divide and Conquer approach:

class Solution {
    public String longestNiceSubstring(String s) {
        if (s.length() < 2) return "";
        char[] arr = s.toCharArray();
        Set<Character> set = new HashSet<>();
        for (char c: arr) set.add(c);
        for (int i = 0; i < arr.length; i++) {
            char c = arr[i];
            if (set.contains(Character.toUpperCase(c)) && set.contains(Character.toLowerCase(c))) continue;
            String sub1 = longestNiceSubstring(s.substring(0, i));
            String sub2 = longestNiceSubstring(s.substring(i+1));
            return sub1.length() >= sub2.length() ? sub1 : sub2;
        }
        return s; 
    }
}

I understand how it works, but not the intuition behind using a Divide and Conquer approach. In other words, if I revisit the problem again after a few days/weeks after I have forgotten everything about it, I won't be able to realize it is a Divide and Conquer problem.

What is that 'thing' that makes it solvable by a Divide and Conquer approach?

Upvotes: 4

Views: 559

Answers (2)

Optimum
Optimum

Reputation: 146

Divide-And-Conquer, to paraphrase wikipedia, is most appropriate when a problem can be broken down into "2 or more subproblems". The solution here checks that the input string meets the condition, then breaks it in two at each character, and recursively checks the strings meet the condition until there is no solution. Generally, the application of divide-and-conquer is easy to get a feel for when the problem can be subdivided symmetrically, such as in the DeWall algorithm for computing the delaunay triangulation for a set of points (http://vcg.isti.cnr.it/publications/papers/dewall.pdf - cool stuff).

What sets the substring problem apart in this instance is it checks all (edit:) possible viable subdivisions by incrementing the line of subdivision. To clarify for anyone who might be confused, this is necessary because the string can't be split down the middle, else you might be splitting a substring like "aAaA" apart and returning only half of it in the end. This kind of meets the more condition in "two or more problems", but I agree it's not intuitive in this instance.

Hope this helps, I had to learn about this a lot recently while implementing the referenced algorithm. Someone with more experience might have a better answer.

Upvotes: 2

user58697
user58697

Reputation: 7923

This is how the algorithm could be described in plain English:

If the entire string is nice, we are done.

Otherwise, there must be a character which exists in only one case. Such a character naturally divides the string into two substrings. Conquer each of them individually, and compare results.

Edit: BTW, I don't think it is a good example of D&C problem. The point is, once we encounter the first "bad" character, the substring to the left of it is nice. There is no need to descend into it. Just record its length and keep going. A simple loop it is.

Upvotes: 4

Related Questions