how can I make this faster?

Perform a preliminary check if both strings have equal lengths. But that doesn't change the Big-O complexity of the algorithm though.

Your algorithm is O(a * b), where a and b are the lengths of your input strings. You could bring that down to O(n) (linear) by creating a frequency map of your strings, and comparing those maps.

A demo:

import java.util.HashMap;
import java.util.Map;

public class Main {

    public static boolean anagram(String s, String t) {
        // Strings of unequal lengths can't be anagrams
        if(s.length() != t.length()) {
            return false;
        }

        // They're anagrams if both produce the same 'frequency map'
        return frequencyMap(s).equals(frequencyMap(t));
    }

    // For example, returns `{b=3, c=1, a=2}` for the string "aabcbb"
    private static Map<Character, Integer> frequencyMap(String str) {
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        for(char c : str.toLowerCase().toCharArray()) {
            Integer frequency = map.get(c);
            map.put(c, frequency == null ? 1 : frequency+1);
        }
        return map;
    }

    public static void main(String[] args) {
        String s = "Mary";
        String t = "Army";
        System.out.println(anagram(s, t));
        System.out.println(anagram("Aarmy", t));
    }
}

which prints:

true
false

how can I make this faster?

Perform a preliminary check if both strings have equal lengths. But that doesn't change the Big-O complexity of the algorithm though.

Your algorithm is O(a * b) * (a+b), where a and b are the lengths of your input strings. The last (a+b) are the two deleteCharAt(...) operations, making it in all a O(n^3) algorithm. You could bring that down to O(n) (linear) by creating a frequency map of your strings, and comparing those maps.

A demo:

import java.util.HashMap;
import java.util.Map;

public class Main {

    public static boolean anagram(String s, String t) {
        // Strings of unequal lengths can't be anagrams
        if(s.length() != t.length()) {
            return false;
        }

        // They're anagrams if both produce the same 'frequency map'
        return frequencyMap(s).equals(frequencyMap(t));
    }

    // For example, returns `{b=3, c=1, a=2}` for the string "aabcbb"
    private static Map<Character, Integer> frequencyMap(String str) {
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        for(char c : str.toLowerCase().toCharArray()) {
            Integer frequency = map.get(c);
            map.put(c, frequency == null ? 1 : frequency+1);
        }
        return map;
    }

    public static void main(String[] args) {
        String s = "Mary";
        String t = "Army";
        System.out.println(anagram(s, t));
        System.out.println(anagram("Aarmy", t));
    }
}

which prints:

true
false