Validate string coupons which could be combo of other valid coupons

user_3394776 0
Viewed 2448

This is code question asked by Amazon on Hacker Rank. Please help to resolve it.

Code Question At Amazon's annual sale, employees are tasked with generating 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 Bare 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 i-th discount coupon is denoted discounts[i], determine 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 this coupon code can be constructed within the rules of a valid coupon. Checking '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 beginning 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 'Ix', is not valid. There is no rule allowing the addition of different characters to the ends of a string.

Since the string is invalid, append 0 to the answer array. There are no more strings to test, so return [1,0]

Function Description

Complete the function find ValidDiscountCoupons in the editor below.

find ValidDiscountCoupons has the following parameter: string discounts[n]: the discount coupons to validate

Returns int[n]: each element i is 1 if the coupon discounts[il is valid and 0 otherwise

enter image description here enter image description here enter image description here

My solution (only partially correct):

public static List<int> findValidDiscountCoupons(List<string> discounts)
        {
            var r = new List<int>(); // result
            foreach (var s in discounts)
            {
                if (s == "")
                    r.Add(1);
                else if (s.Length == 1)
                    r.Add(0);
                else
                {
                    if (isAllCharCountEven(s) && areCharPairsValid(s))
                        r.Add(1);
                    else
                        r.Add(0);
                }
            }

            return r;
        }

        public static bool areCharPairsValid(string s)
        {
            char[] a = s.ToCharArray();

            int y = a.Length;

            for (int x = 0; x < y; x++)
            {
                if (x + 1 < y && a[x] == a[x + 1])
                {
                    // two valid characteres together
                    x++;
                }
                else if (a[x] == a[y - 1])
                {
                    // chars at the front and the end of array match
                    y--;
                }
                else
                {
                    return false;
                }
            }

            return true;
        }

        public static bool isAllCharCountEven(string s)
        {
            while (s.Length > 0)
            {
                int count = 0;
                for (int j = 0; j < s.Length; j++)
                {
                    if (s[0] == s[j])
                    {
                        count++;
                    }
                }

                if (count % 2 != 0)
                    return false;

                s = s.Replace(s[0].ToString(), string.Empty);
            }

            return true;
        }

https://github.com/sam-klok/DiscountCouponesValidation

arrays algorithm string
6 Answers
    private static bool _IsValid(string input)
    {
        //When input is empty
        if (String.IsNullOrEmpty(input))
        {
            return true;
        }

        //When input is only one character
        if (input.Length == 1)
        {
            return false;
        }

        char[] inputChar = input.ToCharArray();

        //When input is two same characters
        if (input.Length == 2)
        {
            if (inputChar[0] == inputChar[1])
            {
                return true;
            }
            else
            {
                return false;
            }
        }

        //When input is > two character
        if (input.Length > 2)
        {
            //Split into two inputs
            for (int i = input.Length - 1; i > 0; i--)
            {
                if (inputChar[0] == inputChar[i])
                {
                    //Get first part
                    bool first = _IsValid(input[1..i]);

                    //Get second part
                    bool second = true;
                    if (first && i + 1 != input.Length)
                    {
                        second = _IsValid(input[(i + 1)..input.Length]);
                    }

                    return first && second;
                }
            }
        }
        return false;
  }
user_120697410 
public static void main(String[] args) {
    List<String> req = new ArrayList<>();
    req.add("abbacc");
    req.add("abba");
    req.add("abca");
    req.add("daabbd");
    req.add("edabbaaccade");
    System.out.println(findValidDiscountCoupons(req)); 
}

public static List<Integer> findValidDiscountCoupons(List<String> discounts){
    List<Integer> res = new ArrayList<>();

    for(String s: discounts){
        if(checkIfCouponValid(s)){
            res.add(1);
        } else {
            res.add(0);
        }
    }

    return res;
}

public static boolean checkIfCouponValid(String coupon){

    // check if string is empty -> return true
    if(coupon.length() == 0){
        return true;
    }

    // check if string length is odd -> return false
    else if(coupon.length() % 2 == 1) {
        return false;
    }

    
    else {

        // divide string into 2 and check both strings
        for(int i=2; i<coupon.length(); i += 2){

            String x = coupon.substring(0,i);
            String y = coupon.substring(i, coupon.length());
            
            // check string 1
            boolean validX = checkIfCouponValid(x);
    
            // check string 2
            boolean validY = checkIfCouponValid(y);
    
            // if both true -> return true
            if(validX && validY){
                return true;
            } 
        }
            
                
        // if first and last character of string are equal then remove them
        int left = 0;
        int right = coupon.length()-1;
        boolean removedAtleaseOneChar = false;
        
        if(coupon.charAt(left) == coupon.charAt(right)){
            left++;
            right--;
            removedAtleaseOneChar = true;
        }
        
        // If character not removed then string is not valid
        if(!removedAtleaseOneChar){
            return false;
        } else {
            coupon = coupon.substring(left, right+1);
        }
        
        return checkIfCouponValid(coupon);

    }

}
user_106275400 
// test cases that pass: {"aabb","cbaabc","ccccaa","aabbceec"}

bool ValidDiscounts::isValid(string coupon) {
    int len=coupon.length();

    if(len==0)
    {
            return true;
    }
    if(len&1)
    {
            //odd number length
            return false;
    }
    if(len==2)
    {
            if(coupon.at(0)==coupon.at(1))
                    return true;
            else
                    return false;
    }

    // find out the longest valid coupon
    for(int idx=len/2; idx>0; idx--)
    {
            string str1=coupon.substr(0,idx);
            string str2=coupon.substr(idx,idx);
            string rstr2=string(str2.rbegin(),str2.rend());
            if(str1==rstr2)
            {
                    //Found a valid coupon at first part. Check the second part
                    if(idx==len/2)
                            return true;
                    int secHalf=(len-2*idx)/2;
                    string stra=coupon.substr(2*idx,secHalf);
                    string strb=coupon.substr(2*idx+secHalf,secHalf);
                    string rstrb=string(strb.rbegin(),strb.rend());
                    if(stra==rstrb)
                            return true;
                    else
                            return false;
            }
    }
    return false;
}
user_18436930

Javascript Solution

Tested with "abba", "abca", "abbacbbc", "aabb", "xaaxybbyzccz", "vaas", "jay", "abbaccddbbaa",

function isValid(str) {
  if (str === "") return true;
  if (str.length % 2 !== 0) return false;
  const stack = [];
  for (const l of str) {
    if (stack.length && l === stack[stack.length - 1]) {
      stack.pop();
    } else {
      stack.push(l);
    }
  }
  if (stack.length === 0) {
    return true;
  } else {
    return false;
  }
}

function discountCoupon(discounts) {
  const res = [];
  for (const d of discounts) {
    if (isValid(d)) {
      res.push(1);
    } else {
      res.push(0);
    }
  }
  return res;
}

const discounts = [
  "abba",
  "abca",
  "abbacbbc",
  "aabb",
  "xaaxybbyzccz",
  "vaas",
  "jay",
  "abbaccddbbaa",
];

console.log(discountCoupon(discounts));

user_102201840

You can find this question here: https://algo.monster/problems/amazon_oa_valid_coupons

Below is my solution and it passed all the test cases on algo.monster:

What I do is that for every character(i) I check if the imediate next one (j = i+1) or any of the consecutive even characters (j+2, j+4 ....) from j are equal to i.

I do this for every character in the string. if all the characters pass this check then its a valid coupon.

Ex:-

aa is valid since the i and j are same

abba is valid because for a the next a is present at the 4th position which is an even distance away from a and we have established that bb is also valid.

lly ee and cddc is also valid. Now if you join ee,cddc and abba in any order that also passes the above condition which corresponds to the 3rd condition mentioned in the question. Example: eecddcabba

All the condition mentioned in the question corresponds to this one condition.

public static boolean check(String coupon){
    boolean[] arr = new boolean[coupon.length()];
    char[] charArr = coupon.toCharArray();
    for(int i=0; i<charArr.length; i++){
        if(arr[i]){
            continue;
        }
        int j = i+1;
        while(j < charArr.length){
            if(charArr[i]==charArr[j]){
                arr[i] = true;
                arr[j] = true;
                break;
            }
            j = j+2;
        }
    }
    for (boolean b : arr) {
        if (!b) {
            return false;
        }
    }
    return true;
}
public static List<Integer> coupons(List<String> discounts) {
    // WRITE YOUR BRILLIANT CODE HERE
    List<Integer> ret = new ArrayList<>(discounts.size());
    for(String s: discounts){
        if(s.isEmpty()){
            ret.add(1);
        }else if(s.length()%2!=0){
            ret.add(0);
        }else if(check(s)){
            ret.add(1);
        }else{
            ret.add(0);
        }
    }
    return ret;
}
user_65834320

Here is the simple implemenntation with stack based approch in Java. With complexcity of O(n*k/2) and Space Complexcity O(k/2). Where N= number of coupons and k is number of characters in a coupan

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Coupan {
  public static void main(String[] args) {
    List<String> req = new ArrayList<>();
    req.add("abba");
    req.add("abca");
    req.add("daabbd");
    req.add("edabbaaccade");
    req.add("e");
    req.add("");
    req.add("eq");
    req.add("ee");
    System.out.println(findValidDiscountCoupons(req));
  }

  private static List<Integer> findValidDiscountCoupons(List<String> coupons) {
    List<Integer> results = new ArrayList<>();

    coupan_loop: for (String coupan : coupons) {
      int coupanLength = coupan.length();

      if (coupanLength == 0) {
        results.add(1);
        continue coupan_loop;
      }
      if (coupanLength == 1 || coupanLength % 2 != 0) {
        results.add(0);
        continue coupan_loop;
      }

      Stack<Character> charecterStack = new Stack<>();
      char[] charArray = coupan.toCharArray();
      charecterStack.add(charArray[0]);
      int coupanHlafLength = coupanLength / 2;

      coupan_char_loop: for (int i = 1; i < charArray.length; i++) {
        if (i + 1 == coupanHlafLength && charecterStack.size() == coupanHlafLength) {
          break coupan_char_loop;
        }
        char previousChar = charecterStack.peek();
        if (previousChar == charArray[i]) {
          charecterStack.pop();
        } else {
          charecterStack.push(charArray[i]);
        }
      }

      if (charecterStack.isEmpty()) {
        results.add(1);
      } else {
        results.add(0);
      }
    }

    return results;
  }

}
user_101325430
Related