{"size": 2951, "ext": "js", "max_stars_repo_path": "leetcode/amazon/coupons.js", "max_stars_repo_name": "brianshen1990/KeepLearning", "max_stars_repo_stars_event_min_datetime": "2021-02-23T07:42:31.000Z", "max_stars_repo_stars_event_max_datetime": "2021-12-16T22:16:28.000Z", "max_issues_repo_path": "leetcode/amazon/coupons.js", "max_issues_repo_name": "brianshen1990/KeepLearning", "max_issues_repo_issues_event_min_datetime": null, "max_issues_repo_issues_event_max_datetime": null, "max_forks_repo_path": "leetcode/amazon/coupons.js", "max_forks_repo_name": "brianshen1990/KeepLearning", "max_forks_repo_forks_event_min_datetime": null, "max_forks_repo_forks_event_max_datetime": null}
{"max_stars_count": 4, "max_issues_count": null, "max_forks_count": null, "avg_line_length": 41.5633802817, "max_line_length": 283, "alphanum_fraction": 0.652321247}
/**

At Amazon's anuual sale, employees are tasked with generaying valid discount coupons for loyal customers. However, there are some used/invalid coupons in the mix, and the challenge in this task is to determine whether a given discount coupon is valid or not.

the validity of a discount coupon is determined as follows:
1. an empty discount coupon is valid
2. if a discount coupon A is valid, then a discount coupon C made by adding one character x to both the beginning of A and the end of A is also valid ( i.e. the discount coupon C=  xAx is valid )
3. if two discount coupons A and B are valid, then the concatenation of B and A is also valid (i.e the coupons AB and BA are both valid).

Given n discount coupons, each coupon consisting of only lowercase English characters, where the ith discount coupon is denoted dicounts[i], determin if each discount coupon is valid or not. A valid coupon is denoted by 1 in the answer array while an invalid coupon is denoted by 0. 

Example

discounts = ['abba', 'abca']

Check if the coupon code can be constrcuted within the rules of a valid coupon.
Chceking 'abba'

- the empty string is valid per the first rule
- Under the second rule, the same character can be added to the beginning and end of a valid coupon code. Add 'b' to the begining and end of the empty string to have 'bb', a valid code
- Using the same rule, 'a' is added to the beginning and end of the 'bb' coupon string. Again, the string is valid

the string is valid, so the answer array is [1]

checking 'abca'
- Using rule 2, a letter can be added to both ends of a string without altering its validity, The 'a' added to the beginning and end of 'bc' does not change its validity
- the remaining string 'bc', is not valid, there is no rule allowing the addition of different characters to ends of a string

so answer is [1, 0]

 */

const findValidDiscountCoupons = (discounts) => {

    const cachePalindra = {};
    const isParlindra = (str) => {
        if ( str in cachePalindra ) return cachePalindra[str];
        for ( let i = 0 ; i < str.length / 2; i++ ) {
            if ( str[i] !== str[str.length-1-i] ) {
                cachePalindra[str] = false;
                return false;
            }
        }
        cachePalindra[str] = true;
        return true;
    }

    const cacheCoupon = {};
    const helper = (str) => {
        if ( str in cacheCoupon ) {
            return cacheCoupon[str];
        }
        if ( str.length % 2 !== 0 ) {
            cacheCoupon[str] = 0;
            return 0;
        }
        
        for ( let i = 0 ; i < str.length ; i += 2 ) {
            if ( isParlindra(str.substr(0, i)) && isParlindra(str.substring(i)) ) {
                cacheCoupon[str] = 1;
                return 1;
            }
        }
        cacheCoupon[str] = 0;
        return 0;
    }
    return discounts.map( discount => helper(discount) );

}

console.log(findValidDiscountCoupons(['abba', 'abca']))