Grokking Data Structures & Algorithms for Coding Interviews
Vote

0% completed

​

Solution: Longest Nice Substring

Problem Statement

Given a string str, return the longest nice substring of a given string.

A substring is considered nice if for every lowercase letter in the substring, its uppercase counterpart is also present, and vice versa. Fo example "AaBbB" is a nice string as A and a present, and B and b present.

If there are multiple, return the substring of the earliest occurrence. If no such string exists, return an empty string.

Examples

  1. Example 1:
    • Input: "BbCcXxY"
    • Expected Output: "BbCcXx"
    • Justification: Here, `"BbCcXx"

.....

.....

.....

Like the course? Get enrolled and start learning!
Venkata Narayanan

Venkata Narayanan

· 3 years ago

Given solution did not work for "xLeElzxgHzcWslEdgMGwEOZCXwwDMwcEhgJHLL" . Getting time limit exceeded error.

Castor Will

Castor Will

· 2 years ago

import (
    "unicode"
)

// Solution struct for encapsulating the algorithm
type Solution struct{}

func (s Solution) findLongestNiceSubstring(str string) string {
    var result string
    for i := 0; i < len(str); i++ {
       var lowerBits, upperBits int
       for j := i; j < len(str); j++ {
          if unicode.IsLower(rune(str[j])) {
             lowerBits |= 1 << (str[j] - 'a')
          } else {
             upperBits |= 1 << (str[j] - 'A')
          }
          if lowerBits == upperBits && j-i+1 > len(result) {
             result = str[i : j+1]
          }
       }
    }
    return result
}
gajendra bora

gajendra bora

· 5 months ago

public String NiceString(String ss) {
        int len = ss.length();
        if (len == 0) {
            return ss;
        }
        int startIndex = 0;
        int maxSize = 0;
        int maxStartSize = 0;
        int endIndex = 0;
        char expectedChar = '\0';
        boolean isNewChar = true;
        for (int index = 0; index < ss.length(); index++) {
            if (isNewChar) {
                expectedChar = getExpectedChar(ss, index);
                isNewChar = false;
            } else {
                if (ss.charAt(index) != expectedChar){
                    if (endIndex - startIndex > maxSize) {
                        maxSize = endIndex - startIndex;
                        maxStartSize = startIndex;
                    }
                    startIndex = index +