Example: Review Score - rFronteddu/general_wiki GitHub Wiki

A website allows customers to add reviews for the products they bought from their store. The review must follow the community guidelines in order to be published. Suppose that the website has marked n strings that are prohibited in reviews. They assign a score to each review that denotes how well it follows the guidelines. The score of a review is defined as the longest contiguous substring of the review which does not contain any string among the list of words from the prohibited list, ignoring the case.

Given a review and a list of prohibited string, calculate the review score.

Function Description

  • findReviewScore has the following parameters:
    • review: a string
    • string prohibitedWords[n]: the prohibited words Returns
    • int: the score of the review

Approach

  1. Iterate over all possible substrings of the review.
  2. For each substring, check if it contains any prohibited word.
  3. Keep track of the longest substring that doesn't contain any prohibited word.

Improved version

We can improve it significantly by using a sliding window technique combined with a set of prohibited words. This approach reduces the complexity to approximately O(n²) or better, depending on the implementation of substring matching.

import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution {

    public int findReviewScore (String review, List<String> prohibitedWords) {
        // Convert prohibited words to a set for fast lookup
        Set<String> prohibitedSet = new HashSet<>();
        for (String word : prohibitedWords) {
            prohibitedSet.add (word.toLowerCase());
        }
        
        // Convert review to lower case for case insensitivity
        String lowerReview = review.toLowerCase();
        int n = lowerReview.length();
        int maxScore = 0;

        // Use sliding window technique to find the longest valid substring
        for (int i = 0; i < n; i++) {
            // use string builder instead of building a new string each time
            StringBuilder currentSubstring = new StringBuilder();
            for (int j = i; j < n; j++) {
                currentSubstring.append (lowerReview.charAt(j));
                if (containsProhibitedWord (currentSubstring.toString(), prohibitedSet)) {
                    break; // Stop expanding this window as it contains a prohibited word
                }
                maxScore = Math.max (maxScore, currentSubstring.length());
            }
        }

        return maxScore;
    }

    // Function to check if a substring contains any prohibited word
    private boolean containsProhibitedWord(String subStr, Set<String> prohibitedSet) {
        for (String word : prohibitedSet) {
            if (subStr.contains(word)) {
                return true;
            }
        }
        return false;
    }
}

Brute force

import java.util.List;

public class Solution {

    public int findReviewScore(String review, List<String> prohibitedWords) {
        // Convert review to lower case for case insensitivity
        String lowerReview = review.toLowerCase();
        
        // Convert prohibited words to lower case
        for (int i = 0; i < prohibitedWords.size(); i++) {
            prohibitedWords.set (i, prohibitedWords.get(i).toLowerCase());
        }
        
        int n = review.length();
        int maxScore = 0;

        // Try all possible substrings of the review
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                String subStr = lowerReview.substring (i, j + 1);
                
                // Check if the substring contains any prohibited word
                if (!containsProhibitedWord (subStr, prohibitedWords)) {
                    // Update maxScore if this substring is longer
                    maxScore = Math.max (maxScore, subStr.length());
                }
            }
        }
        
        return maxScore;
    }

    // Function to check if a substring contains any prohibited word
    private boolean containsProhibitedWord(String subStr, List<String> prohibitedWords) {
        for (String word : prohibitedWords) {
            if (subStr.contains (word)) {
                return true; 
            }
        }
        // Does not contain any prohibited word
        return false; 
    }
}
⚠️ **GitHub.com Fallback** ⚠️